java组合的算法

从m个数里面取n个数的算法:

这里只说一种.网上也有例子.

题目:

1到19取任意个数字,求和为20的组合.

 

算法分析：

1，定义两个数组，一个存放真实的值--（arrVal），一个存放每个值对应的flag--（arrFlag）；

    （这里也可以用一个数组，可以用arrFlag数组下标代替1到19，有无缺点自己可以去衡量下，主要看自己的需求。）

2，arrFlag（存放flag的数组），值为0代表arrVal数组对应下标的值没有被选中，反之，值为1被选中。

3，初期化，将arrFlag数组的前n个值设置为1，代表第一个组合。

4，从左到右开始扫描arrFlag数组，将第一个“10”组合转为“01”组合，并且将其左边的1全部移动到数组的最左端，这样改变后算一组组合。

     示例：    011100 ⇒ 011010（先将“10”变为“01”） ⇒110010（再将“1”全部移动到数组的最左端）

5，当数组没有“10”组合时，也就是说n个1全部移动到最右端时，遍历结束。

     示例：    000111表示遍历结束

 

程序解析：

1，定义两个数组，一个存放真实的值--（arrVal），一个存放每个值对应的flag--（arrFlag）；

（这里也可以用一个数组，可以用arrFlag数组下标代替1到19，有无缺点自己可以去衡量下，主要看自己的需求。）

可以参照这个对照程序看.

    /** 常量定义 */
	// 和为20
    private static final int SUM = 20;
    // 数组长度 = 19
    private static final int ARR_LENGTH = 19;
    // 存放真实值的数组
    private static final int[] arrVal = new int[ARR_LENGTH];
    // 存放标记的数组
    private static int[] arrFlag = new int[ARR_LENGTH];
    // 存放真实值的数组初期化
    static {
        for (int i = 0; i < ARR_LENGTH; i++) {
            arrVal[i] = i + 1;
        }
    }

 2，程序的入口方法main()

     求和至少2个数,最多ARR_LENGTH个数

 

    public static void main(String[] args) {
        for (int i = 2; i <= ARR_LENGTH; i++) {
            assemble(i);
        }
    }

 3,组合的方法

    /**
     * 组合.
     * 
     * @param num 组合的个数
     */
    private static void assemble(int num) {
        // 初期化flag数组，将arrFlag数组的前n个值设置为1，代表第一个组合。
        initArrFlag(num);

        // 判断第一组组合是否满足需求
        if (isRequired()) {
            print();
        }

        // 遍历结束flag（true：结束，false:未结束）
        boolean endFlag = false;
        while (!endFlag) {
            // 第一次出现"10"的位置左端出现1的个数
            int sumOne = 0;

            for (int i = 0; i < ARR_LENGTH - 1; i++) {
                if(arrFlag[i] == 1) {
                    sumOne++;
                }

                // 找出第一次出现"10"的位置
                if (arrFlag[i] == 1 && arrFlag[i + 1] == 0) {
                    // 将"10"改变为"01"
                    arrFlag[i] = 0;
                    arrFlag[i + 1] = 1;

                    // 将该位置左侧的1全部移动到最左端
                    for(int j = 0; j < i; j++) {
                        if(j < sumOne - 1) { // 注意：此处要-1，因为包含了"10"的这个1
                            arrFlag[j] = 1;
                        } else {
                            arrFlag[j] = 0;
                        }
                    }
                    endFlag = false;
                    break;
                }

                endFlag = true;
            }

            // 判断新组合是否满足需求
            if (isRequired()) {
                print();
            }
        }
    }

 4,下面是一些辅助方法。

 

    /**
     * 初期化flag数组，将arrFlag数组的前n个值设置为1。
     * 
     * @param num 组合的个数
     */
    private static void initArrFlag(int num) {
        for (int i = 0; i < ARR_LENGTH; i++) {
            if(i < num) {
                arrFlag[i] = 1;
            } else {
                arrFlag[i] = 0;
            }
        }
    }

    /**
     * 判断组合是否满足需求。
     * 
     * @return true:满足， false:不满足
     */
    private static boolean isRequired() {
        int sum = 0;
        for (int i = 0; i < ARR_LENGTH; i++) {
            if (arrFlag[i] == 1) {
                sum += arrVal[i];
            }
        }

        if (sum == SUM) {
            return true;
        }
        return false;
    }

    /**
     * 输出组合。
     */
    private static void print() {
        System.out.println();
        for (int i = 0; i < ARR_LENGTH; i++) {
            if (arrFlag[i] == 1) {
                System.out.print(arrVal[i] + ", ");
            }
        }
    }