005-01 C++のnext_permutation、prev_permutation

C#で、C++のnext_permutationとprev_permutationを実装します。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.WriteLine("■■■昇順の列挙■■■");
        string[] BaseArr1 = new string[] { "1", "2", "3" };
        foreach (string[] EachStrArr in CppPermutationClass<string>.DerivePermutation(BaseArr1)) {
            Array.ForEach(EachStrArr, pX => Console.Write(pX));
            Console.WriteLine();
        }

        Console.WriteLine("■■■降順の列挙■■■");
        string[] BaseArr2 = new string[] { "3", "2", "1" };
        do {
            Array.ForEach(BaseArr2, pX => Console.Write(pX));
            Console.WriteLine();
        } while (CppPermutationClass<string>.PrevPermutation(ref BaseArr2));
    }
}

#region CppPermutationClass
internal static class CppPermutationClass<Type> where Type : IComparable
{
    // C++のNextPermutationの結果の列挙を返す
    internal static IEnumerable<Type[]> DerivePermutation(IEnumerable<Type> pEnum)
    {
        Type[] wkArr = pEnum.ToArray();
        do {
            yield return wkArr;
        } while (NextPermutation(ref wkArr));
    }

    // C++のNextPermutationを模倣
    internal static bool NextPermutation(ref Type[] pArr)
    {
        // 右から左に見ていき、初めて小さくなった要素を求める
        int WillChangeInd = -1;
        for (int I = pArr.GetUpperBound(0) - 1; I >= 0; I--) {
            if (pArr[I].CompareTo(pArr[I + 1]) < 0) {
                WillChangeInd = I;
                break;
            }
        }

        if (WillChangeInd == -1) {
            return false;
        }

        // 初めて小さくなった要素より右の変更すべき要素を求める
        int MinValInd = WillChangeInd + 1;
        for (int I = WillChangeInd + 2; I <= pArr.GetUpperBound(0); I++) {
            if (pArr[WillChangeInd].CompareTo(pArr[I]) >= 0) continue;

            if (pArr[MinValInd].CompareTo(pArr[I]) >= 0) {
                MinValInd = I;
            }
        }

        // 変更すべき要素と3角交換
        Type wkStr = pArr[WillChangeInd];
        pArr[WillChangeInd] = pArr[MinValInd];
        pArr[MinValInd] = wkStr;

        // 正順で連結
        var ResultList = new List<Type>();
        for (int I = 0; I <= WillChangeInd; I++) {
            ResultList.Add(pArr[I]);
        }
        // 逆順で連結
        for (int I = pArr.GetUpperBound(0); I >= WillChangeInd + 1; I--) {
            ResultList.Add(pArr[I]);
        }

        pArr = ResultList.ToArray();
        return true;
    }

    // C++のPrevPermutationを模倣
    internal static bool PrevPermutation(ref Type[] pArr)
    {
        // 右から左に見ていき、初めて大きくなった要素を求める
        int WillChangeInd = -1;
        for (int I = pArr.GetUpperBound(0) - 1; I >= 0; I--) {
            if (pArr[I].CompareTo(pArr[I + 1]) > 0) {
                WillChangeInd = I;
                break;
            }
        }

        if (WillChangeInd == -1) {
            return false;
        }

        // 初めて大きくなった要素より右の変更すべき要素を求める
        int MinValInd = WillChangeInd + 1;
        for (int I = WillChangeInd + 2; I <= pArr.GetUpperBound(0); I++) {
            if (pArr[WillChangeInd].CompareTo(pArr[I]) <= 0) continue;

            if (pArr[MinValInd].CompareTo(pArr[I]) <= 0) {
                MinValInd = I;
            }
        }

        // 変更すべき要素と3角交換
        Type wkStr = pArr[WillChangeInd];
        pArr[WillChangeInd] = pArr[MinValInd];
        pArr[MinValInd] = wkStr;

        // 正順で連結
        var ResultList = new List<Type>();
        for (int I = 0; I <= WillChangeInd; I++) {
            ResultList.Add(pArr[I]);
        }
        // 逆順で連結
        for (int I = pArr.GetUpperBound(0); I >= WillChangeInd + 1; I--) {
            ResultList.Add(pArr[I]);
        }

        pArr = ResultList.ToArray();
        return true;
    }
}
#endregion

実行結果

■■■昇順の列挙■■■
123
132
213
231
312
321
■■■降順の列挙■■■
321
312
231
213
132
123

解説

C#のサンプル集 8-17 辞書順式で次の順列を求めるをベースにしてます。