8-17 辞書順式で次の順列を求める

問題

ある順列が与えられたとき、辞書式順で次の順列を求める方法があります。

●与えられた順列を右から左に見ていき、初めて小さくなった要素が変更すべき要素である。
  例えば、与えられた順列が31420であれば、1が変更すべき要素である。
  (その右の420は0と2と4でできる順列の辞書式順で最後のものであるため)
●変更すべき要素(1)の右の部分(420)にある要素で、
  1の次に大きいもの(2)を探し、それを変更すべき要素と入れ替える。順列は32410となる。
  ここで、410の部分を、0と1と4でできる順列の辞書式順で最初のものに置き換える。
  (それには、単純に410を逆順に並べ替えればよい)
  これが、最初に与えられた順列の、辞書式順の次の順列である。
これをプログラムにして下さい。

再帰の技法の31ページの練習問題を参考にさせていただきました。

ソース

using System;

class Program
{
    static void Main()
    {
        //string CurrJyunretu = "31420";
        string CurrJyunretu = "01234";

        for (int I = 0; I <= 5 * 4 * 3 * 2; I++) {
            string NextJyunretu = getNextJyunretu(CurrJyunretu);
            Console.WriteLine("{0}の次の順列は、{1}", CurrJyunretu, NextJyunretu);
            if (NextJyunretu.Contains("順列の最後")) return;
            CurrJyunretu = NextJyunretu;
        }
    }

    static string getNextJyunretu(string pTarget)
    {
        //右から左に見ていき、初めて小さくなった要素を求める
        int WillChangeInd = -1;
        char[] wkCharArr = pTarget.ToCharArray();
        for (int I = wkCharArr.GetUpperBound(0) - 1; I >= 0; I--) {
            if (wkCharArr[I] < wkCharArr[I + 1]) {
                WillChangeInd = I;
                break;
            }
        }

        if (WillChangeInd == -1) return "なし(順列の最後に到達)";

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

            if (wkCharArr[MinCharInd] >= wkCharArr[I]) {
                MinCharInd = I;
            }
        }

        //変更すべき要素と3角交換
        char WKChar = wkCharArr[WillChangeInd];
        wkCharArr[WillChangeInd] = wkCharArr[MinCharInd];
        wkCharArr[MinCharInd] = WKChar;

        //正順で連結
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= WillChangeInd; I++) {
            sb.Append(wkCharArr[I]);
        }
        //逆順で連結
        for (int I = wkCharArr.GetUpperBound(0); I >= WillChangeInd + 1; I--) {
            sb.Append(wkCharArr[I]);
        }

        return sb.ToString();
    }
}

ソース (深さ優先探索で順列を列挙してから、次の順列を求める)

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

class Program
{
    static void Main()
    {
        string wk = "01234";
        Console.WriteLine("{0}の次の順列は{1}", wk, getNextJyunretu(wk));
    }

    static string getNextJyunretu(string pTarget)
    {
        var query = pTarget.ToCharArray().OrderBy(X => X);
        string BaseStr = "";
        foreach (char each in query) {
            BaseStr += each;
        }

        var stk = new Stack<string>();

        for (int I = 0; I <= BaseStr.Length - 1; I++) {
            stk.Push(BaseStr[I].ToString());
        }

        var answerList = new List<string>();

        while (stk.Count > 0) {
            string wkStr = stk.Pop();

            if (wkStr.Length == BaseStr.Length) {
                answerList.Add(wkStr);
                continue;
            }

            for (int I = 0; I <= BaseStr.Length - 1; I++) {
                if (wkStr.Contains(BaseStr[I].ToString()) == false) {
                    stk.Push(wkStr + BaseStr[I].ToString());
                }
            }
        }

        foreach (string each in answerList.OrderBy(X => X)) {
            if (pTarget.CompareTo(each) >= 0) continue;
            return each;
        }
        return pTarget;
    }
}

実行結果

01234の次の順列は01243

解説

深さ優先探索で順列を列挙してから、次の順列を求める方法も作ってみました。