求n个数中m个数的所有组合

Question

问题描述：
输入：N M（N>=M）
计算：从1，2,3……N中选出M个不重复数
输出：选出的M个数的组合如N=4，M=2；则输出
1,2
1,3
1,4
2,3
2,4
3,4需要递归算法和非递归算法两种不同的实现，希望把原理讲清楚，通俗易懂一点。最好用java语言实现，先谢谢了！

Answer 1

import java.util.Arrays;
public class Combination{private int[] index;//用于存储需要组合的数组的下标的成员变量。
private int length;//表示待组合数组的长度。
private int n;//组合序列的元素个数
private long numLeft;//用于存储剩余组合序列个数的成员变量。
@SuppressWarnings("unused")
private long total;//用于存储组合序列总数的成员变量。public Combination(int length){
this(length,0);
}public Combination(int length,int n){
this.length=length;
this.n=n;
reset();
}public void reset(){if(n>length){
System.out.println("需要组合的个数超出数组元素个数！");
System.exit(1);
}//初始化numLeft，开始时numLeft应该为2^n.
total=numLeft=(int)Math.pow((double)2,(double)length);//初始化数组index。
index=new int[length];
Arrays.fill(index,0);
}private int sum(){
int s=0;
for(int i:index){
s+=i;
}
return s;
}public boolean hasMore(){
return numLeft > 0;
}public int[] getNext(){index[0]+=1;
for(int i=0;i<index.length;i++){
if(index[i]==2){
index[i]=0;
if(i!=index.length-1) index[i+1]+=1;
}
}
numLeft--;
if(this.n!=0){
if(sum()==this.n) return index;
else if(hasMore()) return getNext();
}
return index;
}
}

Answer 2

int l=3,m=2;
int[] iArr=new int[l];
int num=0;
int pos=0;
int ppi=0;
for(;;){
if(num==l){
if(pos==1){
break;
}
pos-=2;
ppi=iArr[pos];
num=ppi;
}
iArr[pos++]=++num;
if(pos!=m){
continue;
}
for(int i=0;i<pos;i++){
System.out.print(iArr[i]+",");
}
System.out.println();
}

Answer 3

public static void main(String[] args) {
solve(4,2);
} private static void solve(int m, int n) {
int[] nums = new int[m];
for (int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
innerSolve(nums, 0, n, "");
} private static void innerSolve(int[] chs, int startIndex, int length,
String result) {
if (startIndex + length > chs.length)
return;
if (length == 0) {
System.out.println(result);
return;
}
for (int i = startIndex; i < chs.length; i++) {
innerSolve(chs, i + 1, length - 1, result + chs[i] + " ");
}
}

Answer 4

组合算法很简单，采用模拟进制进位就可以了
给你一个非递归的例子吧import java.util.*;
class Combine {
    public static void main(String[] args) { 
        combine(5, 3); //N 5， M 3
    }    public static void combine(int n, int m) {
        if (m > n) {m = n;}
        int[] num = new int[n];
        for (int i=0; i<n; i++) {
           num[i] = i+1;
        }
        int[] dig = new int[num.length];
        for (int i=0; i<num.length; i++) { 
            dig[i] = (i<num.length-m) ? 0 : 1;
        }
        List<String> result = new ArrayList<String>();
        while (true) { 
            int cnt=0, end=0;
            for (int i=0; i<dig.length; i++) {
                if (dig[i] == 1) {
                    cnt++;
                    if (i<m) {end++;}
                }
            }
            if (cnt == m) { 
                StringBuilder buf = new StringBuilder();
                for (int i=0; i<num.length; i++) {
                    if (dig[i] == 1) {buf.append(num[i]).append(",");}
                }
                buf.delete(buf.length()-1, buf.length());
                result.add(0, buf.toString());
            }
            if (end == m) {break;}            dig[dig.length-1]++;
            for (int i=dig.length-1; i>0; i--) {
                if (dig[i] == 2) {
                    dig[i] = 0;
                    dig[i-1]++; 
                } else {
                    break; 
                }
            }
        }
        for (String ss : result) {
            System.out.println(ss);
        }
    }
}

Answer 5

 public class Combination {  int n, m;  int[] pre;//previous combination.
  public Combination(int n, int m) {
   this.n = n;
   this.m = m;
  }
  /**
   * 取下一个组合。可避免一次性返回所有的组合(数量巨大，浪费资源)。
   * if return null,所有组合均已取完。
   */
  public int[] next() {
   if (pre == null) {//取第一个组合，以后的所有组合都经上一个组合变化而来。
    pre = new int[n];
    for (int i = 0; i < pre.length; i++) {
     pre[i] = i;
    }
    int[] ret = new int[n];
    System.arraycopy(pre, 0, ret, 0, n);
    return ret;
   }
   int ni = n - 1, maxNi = m - 1;
   while (pre[ni] + 1 > maxNi) {//从右至左，找到有增量空间的位。
    ni--;
    maxNi--;
    if (ni < 0)
     return null;//若未找到，说明了所有的组合均已取完。
   }
   pre[ni]++;
   while (++ni < n) {
    pre[ni] = pre[ni - 1] + 1;
   }
   int[] ret = new int[n];
   System.arraycopy(pre, 0, ret, 0, n);
   return ret;
  }
 }