m選n的所有組合

思路
M選N組合算法
應用--×××的注數(shù)算法

本程序的思路是開一個數(shù)組b，其長度和數(shù)據(jù)數(shù)組一致，其前N位為1，N就是要取的數(shù)的個數(shù)，然后按照b的數(shù)據(jù)為1的下標來取數(shù)據(jù)數(shù)組的數(shù)字
然后從左到右掃描數(shù)組b元素值的“10”組合，找到第一個“10”組合后將其變?yōu)?br/>“01”組合，同時將其左邊的所有“1”全部移動到數(shù)組的最左端，“0”移到所有“1”和變?yōu)榱恕?1”的中間
當b數(shù)組最右邊的N個元素全部為1時 組合完畢
例如求5中選3的組合：
1 2 3 4 5 <-數(shù)組數(shù)組
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
打印所有組合時，做判斷是1時賦值下標然后輸出

public class MyCombine {
public static void main(String[] args) {
String[] a = { "1", "2", "3", "4", "5","6","7","8","9","10","11"};
int num = 5;
MyCombine tp = new MyCombine();
for (String obj : tp.combine(a, num)) {
//System.out.println(obj.toString());
break;
}
}
/**

• 實現(xiàn)的算法
• @param a 數(shù)據(jù)數(shù)組
• @param num M選N中 N的個數(shù)
• @return
  */
  private List<String> combine(String[] a, int num) {
  List<String> list = new ArrayList<String>();
  List<String> list2 = new ArrayList<String>();
  StringBuffer sb = new StringBuffer();
  String[] b = new String[a.length];
  for (int i = 0; i < b.length; i++) {
  if (i < num) {
  b[i] = "1";
  } else
  b[i] = "0";
  }
  for(int i = 0; i < b.length; i++){
  if(b[i]=="1"){
  //list2.add(a[i]);
  System.out.print(a[i]+",");
  }
  }
  System.out.println("\n");
  int point = 0;
  int nextPoint = 0;
  int count = 0;
  int sum = 0;
  String temp = "1";
  while (true) {
  // 判斷是否全部移位完畢
  for (int i = b.length - 1; i >= b.length - num; i--) {
  if (b[i].equals("1"))
  sum += 1;
  }
  // 根據(jù)移位生成數(shù)據(jù)
  for (int i = 0; i < b.length; i++) {
  if (b[i].equals("1")) {
  point = i;
  sb.append(a[point]);
  sb.append(" ");
  count++;
  if (count == num)
  break;
  }
  }
  for(int i = 0; i < b.length; i++){
  if(b[i]=="1"){
  System.out.print(a[i]+",");
  }
  }
  System.out.println("\n");
  // 往返回值列表添加數(shù)據(jù)
  list.add(sb.toString());
  // 當數(shù)組的最后num位全部為1 退出
  if (sum == num) {
  break;
  }
  sum = 0;
  // 修改從左往右第一個10變成01
  for (int i = 0; i < b.length - 1; i++) {
  if (b[i].equals("1") && b[i + 1].equals("0")) {
  point = i;
  nextPoint = i + 1;
  b[point] = "0";
  b[nextPoint] = "1";
  break;
  }
  }
  // 將 i-point個元素的1往前移動 0往后移動
  for (int i = 0; i < point - 1; i++)
  for (int j = i; j < point - 1; j++) {
  if (b[i].equals("0")) {
  temp = b[i];
  b[i] = b[j + 1];
  b[j + 1] = temp;
  }
  }
  // 清空 StringBuffer
  sb.setLength(0);
  count = 0;
  }
  System.out.println("數(shù)據(jù)長度 " + list.size());
  return list;
  }
  }