フルソートアルゴリズム


本文は転載で、原文の住所:http://blog.csdn.net/smile_pxy/article/details/583351
R={r 1,r 2,...,rn}は配列するn個の元素であり,Ri=R−{ri}.集合Xにおける元素の全配列をPerm(X)と記す.(ri)Perm(X)は、全配列Perm(X)の各配列に接頭辞riを付けた配列を表す.Rの全配列は以下のようにまとめられる.
n=1のとき、Perm(R)=(r)であり、rは集合Rの中で唯一の要素である.
n>1の場合、Perm(R)は、(r 1)Perm(R 1)、(r 2)Perm(R 2)、......、(rn)Perm(Rn)からなる
この再帰的定義によれば、Perm(R)を生成する再帰アルゴリズムは以下のように設計される.
template <class Type>

void Perm(Type list[], int k, int m){

    if ( k == m ){

        for ( int i = 0; i <= m; i++)

                    cout << list[i];

        cout << endl;

    }

    else{

        for ( int i = k; i <= m; i ++){

           Swap( list[k],list[i] );

           Perm( list,k + 1, m ) ;

         Swap( list[k], list[i] );

         }

    }

}

template < class Type >

inline void Swap ( Type &a ,Type & b)

{

         Type temp = a; a = b; b = temp;
}