关于算法:组合

7次阅读

共计 1446 个字符，预计需要花费 4 分钟才能阅读完成。

在数学中，咱们学习了，排列组合，排列是有序的，组合是无程序的。在做算法题时，咱们也会遇到这种。
so，明天来理下，怎么写组合。

举个例子，桌子上有 3 个球 A,B,C，咱们取 2 个，无放回的取，有几种状况？算一下：也就是 C(3,2)=3。

那么先理下思路，咱们须要解决哪几个问题：

要怎么示意 3 个数是否被取了呢，我想，弄一个 int 数组把他们的初值置为 0，就像int a = {0,0,0}, 如果他被取了，就把它置为 1，三个 int 别离代表 ABC。
而后就是从箱子里取球, 是组合是吧。
最初，满足条件，输入咱们失去的组合。

第一步，咱们曾经解决了，怎么示意球被取出来了。
第二步，组合：
咱们想下，以下场景：

从桌子上取 A，那么就是 BC 求组合，取 B，就是 AC 求组合，取 C，就是 AB 求组合
持续反复，求 BC 的组合，就是取 B 进去，求 C 的组合，再像这样持续套娃。。。。都是调用的同一个办法，可想而知，是一个递归。

那么定义一个函数，它的作用是 从 a 中取球，取到满足条件输入组合 。再定义一个 index，示意我获得是哪一个球。之后，咱们取球，如果要选，把 a[index] 置为 1，参数 curr 示意曾经取了多少个球，所以也须要 +1，而后再去取下一个球。如此重复。

当然咱们也能够不取这个球，不取这个球，就要把它置为 0，然而须要 index++，因为不取这个球，那还是须要去取下一个球，比方不取 A，然而咱们还是要去 BC。

紧接着找到递归进口，也就是取完 2 个球，或者 3 个球都被取完了。失去之后，就把它打印进去。也就是调用 show(a[])办法。

show 办法: 遍历 i 数组，如果 a[i]==1，即咱们取了，就把他输入。(char)('A'+i)+" "这也是个小细节。

/* 从 5 个小球中取出三个小球 */
public class 组合 {
    static int count;
    // 很显著是一个组合问题, 不必思考排列，排列的话，就能够用全排列
    public static void main(String[] args) {int a[] = {0,0,0};
        method1(a,0,2,0);
        System.out.println(count);
    }

    /**
     * 作用: 从 a 中取球，取到 2 个球有哪几种组合
     *
     * @param a 数组 a 示意以后被选中的数
     * @param index 以后被选中的数的索引
     * @param sum  要选中多少个数
     * @param curr  以后曾经选中了多少个数
     */
    private static void method1(int a[], int index, int sum, int curr) {if (curr == sum){show(a);
            count++;
            return;
        }
        // 如果数组都选完了，就不能选了, 之所以 index == a.length，是因为最初一个也要被选
        if (index == a.length){return;}
        // 以后地位要选，将这个地位改为 1
        a[index] = 1;
        // 判断下一个数是否要选
        method1(a,index+1,sum,curr+1);
        // 以后这个地位不选，将这个地位改为 0
        a[index] = 0;
        method1(a,index+1,sum,curr);

    }

    private static void show(int[] a) {for (int i =0; i < a.length;i++){if (a[i] == 1 ){System.out.print((char)('A'+i)+" ");// 变成 char 与 int 相加为 int，所以再把它变成 char
            }
        }
        System.out.println();}
}

正文完