组合算法 java实现方式

 

import java.util.ArrayList;

import java.util.List;

/**

组合算法(来自互联网，java implement by xiems)

  本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标   

  代表的数被选中，为0则没选中。     

  首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。     

  然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为   

  “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。     

  当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得   

  到了最后一个组合。     

  例如求5中选3的组合：     

  1   1   1   0   0   //1,2,3     

  1   1   0   1   0   //1,2,4     

  1   0   1   1   0   //1,3,4     

  0   1   1   1   0   //2,3,4     

  1   1   0   0   1   //1,2,5     

  1   0   1   0   1   //1,3,5     

  0   1   1   0   1   //2,3,5     

  1   0   0   1   1   //1,4,5     

  0   1   0   1   1   //2,4,5     

  0   0   1   1   1   //3,4,5  

 *

 */

public class CombinationUtil {

public static void main(String[] args) {

//combinate(2, 2);

combinateAll(5);

}

 

/**

* n个数的全组合

* @param n

* @return

*/

public static List<List<Integer>> combinateAll(int n){

List<List<Integer>> resultList = new ArrayList<List<Integer>>();

for (int i = 1; i <= n; i++) {

resultList.addAll(combinate(n, i));

}

return resultList;

}

 

/**

* 从n个数中取m个数的组合

* @param n

* @param m

* @return

*/

public static List<List<Integer>> combinate(int n, int m) {

// 构造初始化字符串，前m位为1，后n-m位为0

String str = "";

for (int i = 0; i < n; i++) {

str += i < m ? "1" : "0";

}

// 最终字符串为后m位为1，前面n-m位为0

String lastStr = str.substring(m) + str.substring(0, m);

// System.out.println(lastStr);

 

List<List<Integer>> resultList = new ArrayList<List<Integer>>();

resultList.add(getIndex(str));

//System.out.println(getIndex(str));

while (!str.equals(lastStr)) {

// 取到第一个10

int index = str.indexOf("10");

// 转换10为01

String suff = "01" + str.substring(index + 2);

// 取10前的字符串

String pre = str.substring(0, index);

// 统计1的个数，用于重新构造前字符串

int count = 0;

for (int i = 0; i < pre.length(); i++) {

if (pre.charAt(i) == '1') {

count++;

}

}

// 重新构造前字符串

String newPre = "";

for (int i = 0; i < pre.length(); i++) {

newPre += i < count ? "1" : "0";

}

str = newPre + suff;

resultList.add(getIndex(str));

}

return resultList;

}

 

/**

* 显示下标组合

* @param str

* @return

*/

private static List<Integer> getIndex(String str) {

List<Integer> indexList = new ArrayList<Integer>();

for (int i = 0; i < str.length(); i++) {

if (str.charAt(i) == '1') {

indexList.add(i);

}

}

System.out.println(indexList);

return indexList;

}

}