全配置と組み合わせ-JAVAバージョン実装
2692 ワード
1全配列
angram(String str)のような関数を書いて、strの全配列を印刷して、abcの全配列のようです:abc、acb、bca、dac、cab、cba
1.1再帰的な実装
便宜上、123を例に挙げます.123の全配列は123,132,213,231,312,321の6種類である.まず、213と321の2つの数がどのように得られたかを考えます.いずれも123のうち1と後の2つの数を交換したことは明らかである.次いで、123の2番目の数と3番目の数とを交換して132を得ることができる.同様に、213および321に従って231および312を得ることができる.したがって、全配列は、最初の数字からそれぞれの数を後ろの数字と交換することであることがわかります.この法則を見つけた後、再帰的な手順は以下の通りです.
1)最初の位置を決定する:最初の要素はそれぞれ後の要素と交換する
2)後ろの位置の全配列を求める
3)ステップ1と2 4を繰り返す)再帰終了条件:要素が1つしかない場合、停止
文字列に重複文字がある場合、上記の方法は間違いなく要求に合致しないので、今から重複する数列を取り除く方法を考えます.
重複する全配列を取り除くのは、全配列が最初の数字から各数をそれぞれ後ろの数字と交換するためである.まず、1つの数が後ろの数字と同じであれば、この2つの数は交換されないという判断を加えてみましょう.122のように、第1の数は、後で212、221に交換される.そして122のうちの2番目の数は3番目の数と交換する必要はないが、212では2番目の数と3番目の数が異なり、交換後221が得られる.122のうちの第1の数と第3の数とを交換した221と重複している.だからこの方法はだめです.換言すれば、122に対して、第1の数1と第2の数2とを交換して212を得、その後、第1の数1と第3の数2を交換することを考慮し、この場合、第3の数は第2の数に等しいため、第1の数は第3の数と交換しない.さらに212を考慮すると、その2番目の数と3番目の数との交換は解決221を得ることができる.全配列生成が完了します.これにより,全配列から重複を取り除くルールも得られた--重複を除く全配列は,最初の数字から各数がそれぞれその後ろに重複しない数字と交換される.
1.2応用
2セット
2.1再帰的な実装
2.2応用
angram(String str)のような関数を書いて、strの全配列を印刷して、abcの全配列のようです:abc、acb、bca、dac、cab、cba
1.1再帰的な実装
便宜上、123を例に挙げます.123の全配列は123,132,213,231,312,321の6種類である.まず、213と321の2つの数がどのように得られたかを考えます.いずれも123のうち1と後の2つの数を交換したことは明らかである.次いで、123の2番目の数と3番目の数とを交換して132を得ることができる.同様に、213および321に従って231および312を得ることができる.したがって、全配列は、最初の数字からそれぞれの数を後ろの数字と交換することであることがわかります.この法則を見つけた後、再帰的な手順は以下の通りです.
1)最初の位置を決定する:最初の要素はそれぞれ後の要素と交換する
2)後ろの位置の全配列を求める
3)ステップ1と2 4を繰り返す)再帰終了条件:要素が1つしかない場合、停止
public void angram(String str){
if(str==null)
return;
angram(str.toCharArray(),0);
}//end angram()
private void angram(char[] a,int pBegin){
//base case
if(pBegin==a.length-1)
display(a);
else{
//
for(int pCh=pBegin;pCh<a.length;pCh++){
// swap pCh and pBegin
swap(a,pBegin,pCh); //abc bac
angram(a,pBegin++); // bac ac
// restore pCh and pBegin
swap(a,pBegin,pCh); // bac abc, a abc
}//end for
}//end else
} //end angram()
private void swap(char[] a,int first,int change){
char temp=a[first];
a[first]=a[change];
a[change]=temp;
}//end swap()
private void display(char[] a){
for(char c:a)
System.out.print(c);
System.out.println();
}//end display()
文字列に重複文字がある場合、上記の方法は間違いなく要求に合致しないので、今から重複する数列を取り除く方法を考えます.
重複する全配列を取り除くのは、全配列が最初の数字から各数をそれぞれ後ろの数字と交換するためである.まず、1つの数が後ろの数字と同じであれば、この2つの数は交換されないという判断を加えてみましょう.122のように、第1の数は、後で212、221に交換される.そして122のうちの2番目の数は3番目の数と交換する必要はないが、212では2番目の数と3番目の数が異なり、交換後221が得られる.122のうちの第1の数と第3の数とを交換した221と重複している.だからこの方法はだめです.換言すれば、122に対して、第1の数1と第2の数2とを交換して212を得、その後、第1の数1と第3の数2を交換することを考慮し、この場合、第3の数は第2の数に等しいため、第1の数は第3の数と交換しない.さらに212を考慮すると、その2番目の数と3番目の数との交換は解決221を得ることができる.全配列生成が完了します.これにより,全配列から重複を取り除くルールも得られた--重複を除く全配列は,最初の数字から各数がそれぞれその後ろに重複しない数字と交換される.
private void angram(char[] a,int pBegin){
//base case
if(pBegin==a.length-1)
display(a);
else{
//
for(int pCh=pBegin;pCh<a.length;pCh++){
if(isSwap(a,pBegin,pCh)){ // [pBegin,pCh] pCh ,
// swap pCh and pBegin
swap(a,pBegin,pCh); //abc bac
angram(a,pBegin++); // bac ac
// restore pCh and pBegin
swap(a,pBegin,pCh); // bac abc, a abc
}//end if
}//end for
}//end else
} //end angram()
// [pBegin,pEnd] pEnd
private boolean isSwap(char[] a,int pBegin,int pEnd){
for(int pMove=pBegin;pMove<=pEnd;pMove++){
if(a[pMove]==a[pEnd])
return false;
}//end for
return true;
}//end isSwap()
1.2応用
2セット
2.1再帰的な実装
2.2応用