C++出力全配列再帰アルゴリズム詳細解釈

中心思想:R={r 1,r 2,...,rn}を配列するn個の元素とし,Ri=R-{ri}とする.Perm(X)は、全配列Perm(X)の各配列の前にプレフィックスriを付けた配列を表す.(1)n=1のとき、Perm(R)=(r)であり、ここでrは集合Rの中で唯一の要素である.(2)n>1の場合、Perm(R)は、(r 1)+Perm(R 1),(r 2)+Perm(R 2),…,(rn)+Perm(Rn)から構成される.
では、具体的なプログラムはどのように実現されますか?実際の例では、1列1,2,3,4があると仮定すると、1,2,3,4の全配列perm({1,2,3,4})=1 perm({2,3,4})+2 perm({1,2,4})+4 perm({1,2,4})+4 perm(1,2,3,3)では、各数を最初の数と交換すれば次のシーケンスが得られるのではないでしょうか.例えば{1,2,3,4}1番目と2番目の数を交換すると,2{1,3,4}が得られるのではないか,次に実際の例を用いてプログラムがどのように動作しているかを説明する.
具体的なアルゴリズムの流れ:
数列:{1,2,3}最初の交換は1{2,3}シーケンス{2,3}をperm関数に再帰し、その後
--再帰{2,3}数列{2,3}1番目と1番目の交換は2{3}を得て、出力1,2,3(このときlow=high、シーケンス{3}は1桁しかないので、出力リストリストリストリストリストリストリストリストリスト)数列{2,3}1番目と1番目の交換は戻ってきて、結果は依然として{2,3}数列{2,3}1番目と2番目の交換は3{2}を得て、出力1,3,2{3,2}また1番目と2番目の交換は戻ってきて、戻り{2,3}—{2,3}再帰完了シーケンスが元の状態に戻る{1,2,3}
数列:{1,2,3}第1と第2の交換は2,{1,3}--再帰{1,3}数列{1,3}第1と第1の交換は1{3}を得て、2,1,3数列{1,3}第1と第1の交換は帰ってきて、結果は依然として{1,3}数列{1,3}第1と第2の交換は3{1}を得て、2,3,1{3,1}また第1と第2の交換は帰ってきて、変数{1,3}—{1,3}再帰完了シーケンス{2,1,3}1番目と2番目の交換シーケンスが元の状態に戻る{1,2,3}
数列:{1,2,3}第1と第3の交換は3,{1,2}--再帰{1,2}数列{1,2}第1と第1の交換は1{2}を得て、出力3,1,2数列{1,2}第1と第1の交換は帰ってきて、結果は依然として{1,2}数列{1,2}第1と第2の交換は2{1}を得て、出力3,2,1{2,1}また第1と第2の交換は帰ってきて、変数{1,2}—{1,2}再帰完了シーケンス{3,1,2}1番目と2番目の交換シーケンスが元の状態に戻る{1,2,3}
アルゴリズムはperm({1,2,3})=1 perm({2,3})+2 perm({1,3})+3 perm({1,2})perm({2,3})=2 perm({3})+3 perm({1,3})=1 perm({3})+3 perm({1,2})=1 perm({2})+2 perm({1,2})+2 perm({1})
c++コード:

#include 
using namespace std;
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void perm(int list[],int low,int high){
    if(low==high){   // low==high ,  list        ,  list
        for(int i=0;i<=low;i++)
            cout<<list[i];
        cout<else{
        for(int i=low;i<=high;i++){//            
            swap(list[i],list[low]); 
            perm(list,low+1,high); //   ,     ,   perm         
            swap(list[i],list[low]);//  ,       ,  ,         
        }
    }
}
int main()
{

int list[]={1,2,3};
perm(list,0,2);
return 0;
}

プログラム結果:

123
132
213
231
321
312