並べ替えを生成するための再帰

Question

階乗のような非常に単純なものを除いて、再帰を見つけるのは非常に分かりません。私は、文字列のすべての順列を印刷したい場合は、ほかの文字列の長さが"abcde"ように、5である私は、再帰が階乗のすべての順列を計算したい場合は、長さ7の順列が

abced 
abdce 
abdec 
abecd 
abedc 
acbde 
acbed 
acdbe 
acdeb 
acebd 
acedb 
adbce 
adbec 
adcbe 
adceb 
adebc 
adecb 
aebcd 
aebdc 
aecbd 
aecdb 
aedbc 
aedcb 
bacde 
baced 
badce 
badec 
baecd 
baedc 
bcade 
bcaed 
... 

する必要があります言うことができます5のように、4,3,2または1である。どのアルゴリズムを使うべきですか？このためにC++ライブラリに関数がありますか？

がプリントアウトは次のようになりますと仮定します

acbd 
bcad 
abc 
bac 
ab 
ba 

Answer 1

再帰アルゴリズムを使用して、ほとんどmathematical inductionようです。最初に、ベースケースを処理し、次にサブ問題パターンを見つける必要があります。

階乗については、​​階乗nと問題を定義します。

1. ベース場合、F(0)=1
2. 副問題パターン、F(n)=n!=n*(n-1)!=n*F(n-1)

および順列のために、セットEの全順列としてP(E)を定義します。

1. ベース場合、P({}) = {{}}
2. 副問題パターン。順列のプロセスを考えてみましょう。私は最初の要素xを選択してから、P(E-x)、次にそれぞれp in P(E-x)、そしてxの順番で、xで始まるすべての順列を返します。xすべての順列、別名P(E)。

next_permutationを使用できます。

そして、上記の思考からのコード例は次のようである：

// generate permutation of {a[st], a[st+1], ..., a[ed]} 
void P(char a[], int st, int ed) { 
    if (st > ed) { puts(a); return; } // nothing to generate 
    for (int i=st; i<=ed; ++i) { 
     swap(a[st], a[i]);   // enumerate first element 
     P(a, st+1, ed); 
     swap(a[st], a[i]);   // recover 
    } 
} 

はhttp://ideone.com/zbawY2でそれを確認してください。