フルソートアルゴリズム
本文は転載で、原文の住所: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)を生成する再帰アルゴリズムは以下のように設計される.
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;
}