全配列アルゴリズムの非再帰的実現と再帰的実現の方法(C++)
4159 ワード
(一)非再帰全配列アルゴリズムの基本思想は:1.すべての配列の中で最も小さい配列Pを見つける.
2.Pより大きくて他より小さい配列Qを見つけました.
3.ループは、最大の配列が見つかるまで、アルゴリズムが終了する第2のステップを実行する.
次に、数学的な方法で説明します.
既知シーケンスP=A 1 A 2 A 3 An(Ai!=Aj、(1<=i<=n,1<=j<=n,i!=j))が与えられる.
Pの最小配列を見つけるPmin=P 1 P 2 P 3 PnはPi>P(i-1)(1Pminから、常に現在得る最大の配列が入力であり、次の配列が得られる.
方法:1.低位から高位(後ろから前へ)まで、「トレンドに合わない」数字を見つけます.すなわち、Piこのようなpiが見つからない場合は,最後の全配列が見つかったことを示し,戻ることができる.
2.P(i+1)P(i+2)Pnの中で、1つのPjを探し当てて、Pj"ちょうど大きい"Pi.
(ちょうど大きいという意味は、P(i+1)P(i+2)PnにおけるPiより大きいすべての元素からなる集合の中で最小の元素を意味する.
3.Pi,Pjの位置を交換する.注意:ここではiとjの値は変更する、PiとPjが変更される.
4.交換後、P 1 P 2 P 3 Pnは正確な後列ではない.第1ステップの検索によると、P(i+1)>P(i+2)>があるからです.>Pn
PiとPjの交換が行われても,この部分の最大の配列である.この配列を逆順(最小の配列となる)にすることが求められる次の配列である.
5.ステップ1で「トレンドに合わない」数字が見つからないまで、ステップ1-4を繰り返す.
(二)再帰演算法E={e 1,...,en}はn個の要素の集合を表し,我々の目標はその集合のすべての配列方式を生成することである.EiをEにおいて除去する元素i以降に得られる集合とし、perm(X)は集合Xにおける元素の配列方式、eiを表す.p e r m(X)は、perm(X)における各配列方式の前面にeiを加えて得られる配列方式を表す.例えば、E={a,b,c}の場合、E 1={b,c},perm(E 1)=(b c,c b),e 1となる.perm (E1) = (a b c, a c b).再帰的な基本部分にはn=1を用いる.要素が1つしかない場合、配列は1つしか生成されないので、perm(E)=(e)であり、eはEの唯一の要素である.n>1の場合、perm(E)=e 1となる.perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) + ⋯ +en .perm (En ).この再帰的定義形式は、n個のperm(X)を用いてperm(E)を定義し、各Xはn−1個の要素を含む.これで、完全な再帰定義に必要な基本部分と再帰部分が完了しました.
n=3であり、E=(a,b,c)である場合、perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})を前述の再帰定義に従って得ることができる.同様に、再帰的にperm({b,c})=b.perm({c})+c.perm({b})が定義ので、a.perm({b,c})=ab.perm({c})+ac.perm({b})=a bとなる.c + ac.b = (a b c, a c b).同じ理屈でb.perm({a,c})=ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a),c.perm ( {a, b}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a).従ってperm(E)＝(a b c,a c b,b a c,b c a,c a b,c b a)である.a.perm({b,c})は実際にはabcとa c bの2つの配列を含み、aはそれらの接頭辞であり、perm({b,c})はそれらの接尾辞である.同様に、ac.perm({b})は、接頭辞がa c、接尾辞がperm({b})の配列を表す.プログラム1−1 0は上記perm(E)の再帰定義をC++関数に変換し,このコードはすべての接頭辞がl i s t[0:k−1]、接尾辞がl i s t[k:m]の配列方式を出力する.Perm(list,0,n−1)を呼び出すとlist[0:n−1]のすべてのnが得られる!この呼び出しではk=0,m=n−1の配列方式であるため、配列方式の接頭辞は空であり、接尾辞はlist[0:n−1]で生成されたすべての配列方式である.k=mの場合、接尾辞l i s t[m]は1つしかないので、list[0:m]は生成される出力である.k
2.Pより大きくて他より小さい配列Qを見つけました.
3.ループは、最大の配列が見つかるまで、アルゴリズムが終了する第2のステップを実行する.
次に、数学的な方法で説明します.
既知シーケンスP=A 1 A 2 A 3 An(Ai!=Aj、(1<=i<=n,1<=j<=n,i!=j))が与えられる.
Pの最小配列を見つけるPmin=P 1 P 2 P 3 PnはPi>P(i-1)(1
方法:1.低位から高位(後ろから前へ)まで、「トレンドに合わない」数字を見つけます.すなわち、Pi
2.P(i+1)P(i+2)Pnの中で、1つのPjを探し当てて、Pj"ちょうど大きい"Pi.
(ちょうど大きいという意味は、P(i+1)P(i+2)PnにおけるPiより大きいすべての元素からなる集合の中で最小の元素を意味する.
3.Pi,Pjの位置を交換する.注意:ここではiとjの値は変更する、PiとPjが変更される.
4.交換後、P 1 P 2 P 3 Pnは正確な後列ではない.第1ステップの検索によると、P(i+1)>P(i+2)>があるからです.>Pn
PiとPjの交換が行われても,この部分の最大の配列である.この配列を逆順(最小の配列となる)にすることが求められる次の配列である.
5.ステップ1で「トレンドに合わない」数字が見つからないまで、ステップ1-4を繰り返す.
// a i j
void swap(int* a,int i,int j)
{
a[i]^=a[j];
a[j]^=a[i];
a[i]^=a[j];
}
// a i j
void reverse(int a[],int i,int j)
{
for(;i {
swap(a,i,j);
}
}
void print(int a[],int length)
{
for(int i=0;i cout< cout<}
// を め、 を
void combination(int a[],int length)
{
if(length<2) return;
bool end=false;
while(true)
{
print(a,length);
int i,j;
//トレンドに わない の きiを つける
for(i=length-2;i>=0;--i)
{
if(a[i] else if(i==0) return;
}
for(j=length-1;j>i;--j)
{
if(a[j]>a[i]) break;
}
swap(a,i,j);
reverse(a,i+1,length-1);
}
} (二)再帰演算法E={e 1,...,en}はn個の要素の集合を表し,我々の目標はその集合のすべての配列方式を生成することである.EiをEにおいて除去する元素i以降に得られる集合とし、perm(X)は集合Xにおける元素の配列方式、eiを表す.p e r m(X)は、perm(X)における各配列方式の前面にeiを加えて得られる配列方式を表す.例えば、E={a,b,c}の場合、E 1={b,c},perm(E 1)=(b c,c b),e 1となる.perm (E1) = (a b c, a c b).再帰的な基本部分にはn=1を用いる.要素が1つしかない場合、配列は1つしか生成されないので、perm(E)=(e)であり、eはEの唯一の要素である.n>1の場合、perm(E)=e 1となる.perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) + ⋯ +en .perm (En ).この再帰的定義形式は、n個のperm(X)を用いてperm(E)を定義し、各Xはn−1個の要素を含む.これで、完全な再帰定義に必要な基本部分と再帰部分が完了しました.
n=3であり、E=(a,b,c)である場合、perm(E)=a.perm({b,c})+b.perm({a,c})+c.perm({a,b})を前述の再帰定義に従って得ることができる.同様に、再帰的にperm({b,c})=b.perm({c})+c.perm({b})が定義ので、a.perm({b,c})=ab.perm({c})+ac.perm({b})=a bとなる.c + ac.b = (a b c, a c b).同じ理屈でb.perm({a,c})=ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a),c.perm ( {a, b}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a).従ってperm(E)＝(a b c,a c b,b a c,b c a,c a b,c b a)である.a.perm({b,c})は実際にはabcとa c bの2つの配列を含み、aはそれらの接頭辞であり、perm({b,c})はそれらの接尾辞である.同様に、ac.perm({b})は、接頭辞がa c、接尾辞がperm({b})の配列を表す.プログラム1−1 0は上記perm(E)の再帰定義をC++関数に変換し,このコードはすべての接頭辞がl i s t[0:k−1]、接尾辞がl i s t[k:m]の配列方式を出力する.Perm(list,0,n−1)を呼び出すとlist[0:n−1]のすべてのnが得られる!この呼び出しではk=0,m=n−1の配列方式であるため、配列方式の接頭辞は空であり、接尾辞はlist[0:n−1]で生成されたすべての配列方式である.k=mの場合、接尾辞l i s t[m]は1つしかないので、list[0:m]は生成される出力である.k
template
inline void Swap(T& a, T& b)
{
// a b
T temp = a; a = b; b = temp;
}
template
void Perm(T list[], int k, int m)
{
// list [k：m ]
int i;
if (k == m)
{
//
for (i = 0; i <= m; i++)
cout << list [i];
cout << endl;
}
else // list[k：m ]
{
//
for (i=k; i <= m; i++)
{
Swap (list[k], list[i]);
Perm (list, k+1, m);
Swap (list [k], list [i]);
}
}
}