【算法】排列组合之M选N（可能是最简的代码）

首先，M选N的算法规则：要从长度为M的数组中选N个数，列出所有组合：

1. 生成一个长度为M的新数组；
2. 初始化新数组，前N位填充为1，其余填充为0；
3. 从左往右，找到第一个【10】，则交换1和0，即替换为0和1；
4. 将替换后的1的左边的所有1移动到最左端；
5. 重复步骤3；
6. 如果没有找到【10】，则结束；

例子：求5中选3的组合，用数学公式计算组合为C5-3=(5x4x3)/(3x2x1)=10，算法穷举法验证：

1 2 3 4 5（原始数组）
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

下面用代码实现：

    /**
     * M选N算法
     */
    public static List m2n(List source, int n) {
        List list = Lists.newArrayList();
        
        // 初始化新数组，长度和原数组一致，并且前n为填充1，其余为0
        int size = source.size();
        Integer[] zero = new Integer[size];
        for (int i = 0; i < size; i++) {
            if (i < n) {
                zero[i] = 1;
            } else {
                zero[i] = 0;
            }
        }

        // 寻找【10】，交换，移动
        for (; ; ) {
            
            // 新数组的1的下标对应原数组的下标，生成结果集
            List sublist = Lists.newArrayList();
            for (int i = 0; i < size; i++) {
                if (zero[i].equals(1)) {
                    sublist.add(source.get(i));
                }
            }
            list.add(sublist);

            // 寻找【10】组合，交换为【01】，如果没找到，则代表已结束
            int i = Joiner.on("").join(zero).indexOf("10");
            if (i == -1) {
                break;
            }
            zero[i] = 0;
            zero[i + 1] = 1;

            // 统计交换后的01位置之前有多少个1，并将其移动到最左端
            long count = Arrays.asList(zero).subList(0, i).stream().filter(o -> o.equals(1)).count();
            for (int j = 0; j < i; j++) {
                if (j < count) {
                    zero[j] = 1;
                } else {
                    zero[j] = 0;
                }
            }
        }
        return list;
    }

欢迎留言指出可以优化更简的地方，谢谢。