/**
* 求 N 個元素中 M 個元素的組合算法:
* 1. 創建一個大小為 N 個元素的數組，前 M 個元素為1，后面的 N-M 個元素為0
* 2. 從左向右找到 10 的元素(前一個元素是1，下一個元素是0), 交換這兩個元素；
* 把此元素前面的所有1都移動到數組的最前面，此為一個組合，輸出.
* 3. 直到前 N-M 個元素都為0，則結束，否則繼續第2步直到結束.
*/
public class Combinatory {
public static void produceCombination(String str, int size) {
if (size > str.length()) { throw new IllegalArgumentException("Size is to large."); }
// 創建一個數組，前size個元素全是1
int[] digit = new int[str.length()];
for (int i = 0; i < size; ++i) {
digit[i] = 1;
}
// 輸出第一組
printCombination(str, digit);
while (!end(digit, digit.length - size)) {
for (int i = 0; i < digit.length - 1; ++i) {
if (digit[i] == 1 && digit[i + 1] == 0) {
// i上是1，i + 1是0，交換
int temp = digit[i];
digit[i] = digit[i + 1];
digit[i + 1] = temp;
// 移動i前面的所有1到最左端
int count = countOf1(digit, i);
for (int j = 0; j < count; ++j) {
digit[j] = 1;
}
for (int j = count; j < i; ++j) {
digit[j] = 0;
}
printCombination(str, digit);
break;
}
}
}
}
// 在下標end前1的個數
private static int countOf1(int[] digit, int end) {
int count = 0;
for (int i = 0; i < end; ++i) {
if (digit[i] == 1) {
++count;
}
}
return count;
}
// 數組中為1的下標對應的字符需要輸出
private static void printCombination(String str, int[] digit) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < digit.length; ++i) {
if (digit[i] == 1) {
sb.append(str.charAt(i));
}
}
System.out.println(sb);
}
// 結束條件：前 size 個元素都是0
private static boolean end(int[] digit, int size) {
int sum = 0;
for (int i = 0; i < size; ++i) {
sum += digit[i];
}
return sum == 0 ? true : false;
}
public static void main(String[] args) {
Combinatory.produceCombination("0123456789", 8);
}
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
import java.util.HashSet;
import java.util.Set;
/**
* 求 N 個元素的全排列算法:
* 1. 創建一個大小為 N 個元素的數組.
* 2. 利用 N 進制，滿 N 加 1的原則，對數組的第0個元素加 1，滿 N 了，則下一個元素值加 1.
* 3. 檢查數組中的元素是否有重復的，如果沒有，則是一個排列.
* 4. 直到數組中的元素為0, 1, 2, ..., N - 1，則結束，否則繼續第2步直到結束.
*/
public class Arrangement {
public static void produceArrangement(String str) {
int[] digit = new int[str.length()];
int base = str.length();
while (!end(digit)) {
++digit[0]; // 第1個元素值加1
// 滿N進1
for (int i = 0; i < digit.length; ++i) {
if (digit[i] == base) {
digit[i] = 0;
++digit[i + 1];
} else {
break;
}
}
if (isArrangement(digit)) {
printArrangement(str, digit);
}
}
}
// 數組中每個元素都不同，則是排列中的一個
private static boolean isArrangement(int[] digit) {
int sum = 0;
int endSum = (0 + digit.length - 1) * digit.length / 2;
for (int i = 0; i < digit.length; ++i) {
sum += digit[i];
}
// 為了減少創建Set，所以判斷一下數組中元素的和是不是結束時元素的和，如果是才再繼續判斷.
if (sum != endSum) {
return false;
} else {
Set<Integer> is = new HashSet<Integer>();
for (int i : digit) {
is.add(i);
}
if (is.size() != digit.length) {
return false;
} else {
return true;
}
}
}
private static void printArrangement(String str, int[] digit) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < digit.length; ++i) {
sb.append(str.charAt(digit[i]));
}
System.out.println(sb);
}
// 如果數組中的元素是 0, 1, 2, ..., digit.length - 1，則結束
private static boolean end(int[] digit) {
for (int i = 0; i < digit.length; ++i) {
if (digit[i] != i) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Arrangement.produceArrangement("012345");
}
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
/**
* 使用遞歸求組合
* 找到第i個元素后面的count - 1個元素的組合
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
public class IterativeCombinatory {
private List result;
private String data;
public IterativeCombinatory(String data, int count) {
this.data = data;
this.result = new ArrayList();
buildCombinatory(0, count);
}
// 使用遞歸求組合
public void buildCombinatory(int index, int count) {
for (int i = index; i < data.length(); i++) {
result.add("" + data.charAt(i));
if (1 == count) {
System.out.println(StringUtil.join(result, "+"));
} else if (i + 1 < data.length()) {
buildCombinatory(i + 1, count - 1); // 在i后面找count-1個的組合
}
result.remove("" + data.charAt(i)); // 滿足一個后移除最后一個
}
}
public static void main(String[] args) {
String str = "123456";
for (int count = 2; count <= str.length(); count++) {
new IterativeCombinatory(str, count);
System.out.println();
}
}
}
class StringUtil {
public static String join(Object[] arr, String separator) {
return join(Arrays.asList(arr), separator);
}
public static String join(Collection collection, String separator) {
StringBuilder sb = new StringBuilder();
separator = separator == null ? "" : separator;
Iterator iter = collection.iterator();
while (iter.hasNext()) {
sb.append(iter.next());
if (iter.hasNext()) {
sb.append(separator);
}
}
return sb.toString();
}
}