Java再帰的に文字列の全配列と全結合を実現する。
組み合わせアルゴリズムの用途が広く、把握する必要があります。敷居を下げるために、本論文では主にアルゴリズムの論理と簡易性に注目しています。アルゴリズムの効率を重視していません。ネットブックの実現と自分の需要を結び付けて、ここには四つの目標があります。
1.すべての要素の全配列:abの全配列はab、ba(順序関連)である。
2.すべての要素の全結合:a bの全結合はa、b、ab(順序は関係ない)である。
3.n個の元素の中からm個の元素を選ぶ組み合わせ方はどれらがありますか?abcの中から2つの要素を選ぶ組み合わせはab、ac、bcです。
4.n個の元素の中からm個の元素を選ぶ配列方式を求めてどれらがありますか?abcの中から2つの元素を選ぶ配列はab、ba、ac、ca、bc、cbです。
n個の要素の中からm個の要素を選択する配列は、実はn個の要素を求める中からm個の要素を選択する組み合わせであり、各組み合わせからなる要素セット(配列)を完全に整列するため、スペル関数であり、例を列挙していない。他の3つの目標はコードを参照する。
1.すべての要素の全配列:abの全配列はab、ba(順序関連)である。
2.すべての要素の全結合:a bの全結合はa、b、ab(順序は関係ない)である。
3.n個の元素の中からm個の元素を選ぶ組み合わせ方はどれらがありますか?abcの中から2つの要素を選ぶ組み合わせはab、ac、bcです。
4.n個の元素の中からm個の元素を選ぶ配列方式を求めてどれらがありますか?abcの中から2つの元素を選ぶ配列はab、ba、ac、ca、bc、cbです。
n個の要素の中からm個の要素を選択する配列は、実はn個の要素を求める中からm個の要素を選択する組み合わせであり、各組み合わせからなる要素セット(配列)を完全に整列するため、スペル関数であり、例を列挙していない。他の3つの目標はコードを参照する。
public final class PermutationCombinationHolder {
/** */
static void combination(char[] chars) {
char[] subchars = new char[chars.length]; //
// ( n) 1 , 2 ... n
for (int i = 0; i < chars.length; ++i) {
final int m = i + 1;
combination(chars, chars.length, m, subchars, m);
}
}
/**
* n m . :
* , i , i-1 m-1 .
* : 1, 2, 3, 4, 5 3 .
* 1) 5 , 4 2 , 4 2 , ;
* 2) 5, 4, 3 2 , 2 , ;
* 3) 4, 3, 2 2 , .
* , 1 2 3 for , 5, m.
* , i-1 m-1 .
*/
static void combination(char[] chars, int n, int m, char[] subchars, int subn) {
if (m == 0) { //
for (int i = 0; i < subn; ++i) {
System.out.print(subchars[i]);
}
System.out.println();
} else {
for (int i = n; i >= m; --i) { //
subchars[m - 1] = chars[i - 1]; //
combination(chars, i - 1, m - 1, subchars, subn); // i-1 m-1
}
}
}
/** */
static void permutation(char[] chars) {
permutation(chars, 0, chars.length - 1);
}
/** begin end */
static void permutation(char[] chars, int begin, int end) {
if (begin == end) { //
for (int i = 0; i < chars.length; ++i) {
System.out.print(chars[i]);
}
System.out.println();
} else {
for (int i = begin; i <= end; ++i) { //
if (canSwap(chars, begin, i)) { //
swap(chars, begin, i); //
permutation(chars, begin + 1, end); //
swap(chars, begin, i); //
}
}
}
}
static void swap(char[] chars, int from, int to) {
char temp = chars[from];
chars[from] = chars[to];
chars[to] = temp;
}
static boolean canSwap(char[] chars, int begin, int end) {
for (int i = begin; i < end; ++i) {
if (chars[i] == chars[end]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
final char[] chars = new char[] {'a', 'b', 'c'};
permutation(chars);
System.out.println("===================");
combination(chars);
}
}
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。