[解決済み] 文字列/整数のすべての並べ換えをリストアップします。

質問

プログラミングの面接でよくある課題（私の面接の経験ではありませんが）は、文字列や整数を取り出して、可能な限りの順列を並べることです。

このような問題をどのように行い、どのような論理で解くのか、例はありますか？

コードスニペットをいくつか見ましたが、コメントや説明が十分でなかったため、フォローしにくいです。

どのように解決するのですか？

まず第一に、以下のような臭いがします。 再帰 勿論

原理も知りたいということでしたので、頑張って人語で説明しました。再帰は、たいていの場合、とても簡単だと思います。2つのステップを把握すればいいだけですから。

1. 最初のステップ
2. 他のすべてのステップ（すべて同じロジックです）

で 人間語 :

要するに

1. 1要素の順列は1要素である。
   
   
2. 要素の集合の順列は、各要素を他の要素の順列と結合したリストである。
   
   

例

セットが1つの要素だけである場合 -->

を返します。

perm(a) -> a

セットが2つの文字を持つ場合： for の各要素を返します。 要素の並べ換えを のように、残りの要素を追加します。

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> バ

さらに：集合の各文字について：文字と > の並べ換えを連結したものを返す。

perm(abc) ->

a + perm(bc) --> abc , アクブ

b + perm(ac) --> バック , ビーシーエー

c + perm(ab) --> キャブ , キャバ

perm(abc..z) -->

a + perm(...), b + perm(......)

....

を発見しました。 疑似コード について http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C#

OK、そしてもっと凝ったものを（そしてc #というタグがついているので）、以下から。 http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : むしろ長いですが、とにかくコピーすることにしましたので、投稿はオリジナルに依存しません。

この関数は文字列を受け取り、その文字列の可能な限りの順列を書き出します。したがって、たとえば "ABC" が供給された場合、その文字列が書き出されるはずです。

abc, acb, bac, bca, cab, cba.

コード

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}