日期:2014-05-20  浏览次数:20673 次

求解java 组合算法
本程序的思路是开一个数组,其下标表示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  


求按照上述写出Java代码,要加注释的,谢谢
并且希望给出排列组合的代码,

------解决方案--------------------
另一种实现方法参考
package com.arithmeticx;


public class Combination {
//will the number of selection
private int sel_count=3;
// 存储字符
// 要取的字符目录位置
private int arr[]=new int[sel_count];
public int n=0;
public String c[] = { "1", "2", "3","4","5","6","7","8","9"};

// 从 { "1", "2", "3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18"};取出11个数进行组合,打印出所有的可能
//j代表要选取的个数,start代表选取的开始位置
public void show(int j, int start) {
for (int i = start; i < c.length; i++) {
this.arr[sel_count-j]=i;
if (j == 1) {
print();
}
if ((j - 1) != 0)
show(j-1,i+1);
else
continue;
}
}
private void print() {
for(int k=0;k<sel_count;k++){
++n;
System.out.printf("%-5s",c[arr[k]]);
}
System.out.println();
}
// 从 { "1", "2", "3","4","5","6","7","8","9"}取出11个数进行组合,打印出所有的可能
public static void main(String[] args) {
Combination c=new Combination();
c.show(c.sel_count, 0);
System.out.println(c.n+"次数");
}
}
------解决方案--------------------
Java code
public static void main(String[] args)
    {
        int[] a = { 1, 1, 1, 0, 0 };
        int i = 0;
        while (true)
        {
            for (int j = 0; j < a.length; j++)
                System.out.print(a[j]);
            System.out.println();
            for (; i < a.length - 1; i++)
            {
                if (a[i] == 1 && a[i + 1] == 0)
                {
                    int tem = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = tem;
                    for (int j = 0, k = 0; j < i; j++)
                    {
                        if (j == k && a[j] == 1)
                        {
                            k++;
                            continue;
                        }
                        if (a[j] == 1)
                        {
                            a[k] = a[j];
                            a[j] = 0;
                            k++;
                        }
                    }
                    i = 0;
                    break;
                }
            }
            if(i != 0)
                break;
        }
    }