面白いアルゴリズム-文字列の全配列
1461 ワード
一、テーマ
文字列を入力し、その文字列のすべての配列を印刷します.例えば、文字列abcを入力します.文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
二、問題を解く構想
1つの文字列を2つの部分から構成されていると見なします.第1の部分はその最初の文字で、第2の部分は後ろのすべての文字です.
文字列全体の配列を求めると、2つのステップと見なすことができます.まず、最初の位置に現れる可能性のあるすべての文字、すなわち、最初の文字と後ろのすべての文字を交換することを求めます.このとき、後ろのすべての文字を2つの部分に分けます.後ろの文字の最初の文字と、この文字の後のすべての文字です.
これは実は典型的な再帰的な考え方です.
三、解題コード
文字列を入力し、その文字列のすべての配列を印刷します.例えば、文字列abcを入力します.文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
二、問題を解く構想
1つの文字列を2つの部分から構成されていると見なします.第1の部分はその最初の文字で、第2の部分は後ろのすべての文字です.
文字列全体の配列を求めると、2つのステップと見なすことができます.まず、最初の位置に現れる可能性のあるすべての文字、すなわち、最初の文字と後ろのすべての文字を交換することを求めます.このとき、後ろのすべての文字を2つの部分に分けます.後ろの文字の最初の文字と、この文字の後のすべての文字です.
これは実は典型的な再帰的な考え方です.
三、解題コード
public class Test {
/**
* : , 。 abc。
* a、b、c abc、acb、bac、bca、cab cba。
*
* @param chars
*/
public static void permutation(char[] chars) {
//
if (chars == null || chars.length < 1) {
return;
}
//
permutation(chars, 0);
}
/**
*
*
* @param chars
* @param begin
*/
public static void permutation(char[] chars, int begin) {
// ,
if (chars.length - 1 == begin) {
System.out.print(new String(chars) + " ");
} else {
char tmp;
// ,
for (int i = begin; i < chars.length; i++) {
//
tmp = chars[begin];
chars[begin] = chars[i];
chars[i] = tmp;
//
permutation(chars, begin + 1);
}
}
}
}