如何快速列出63位二进制中有36个1和27个0的所有二进制组合

Question

000000000000000000000000000000000000000000000000000000000000000

111111111111111111111111111111111111111111111111111111111111111

以上是63位2进制，用哪种方法可以不用遍历列出所有的36个1和27个0的所有二进制组合

例如：

第一组

000000000000000000000000000111111111111111111111111111111111111

第二组....第三组....

求大神帮忙。。。

Answer 1

这是个简单的排列组合，只是你的数据太大，很可能内存扛不住，下面有两种简单的方式处理这种问题 (Java 实现)。

1、暴力迭代搜索

public static List<String> solution0(int zeroNumber, int oneNumber) {
    if ((zeroNumber | oneNumber) < 0) {
        throw new IllegalArgumentException(String.format("The number of zero or one is negative : zero = %s, one = %s.", zeroNumber, oneNumber));
    }
    int sequenceLen = zeroNumber + oneNumber;
    if (sequenceLen == zeroNumber || sequenceLen == oneNumber) {
        String sequence = new String(IntStream.range(0, sequenceLen).map(i -> zeroNumber == 0 ? '1' : '0').toArray(), 0, sequenceLen);
        return Collections.singletonList(sequence);
    }
    /* C(m, m + n)，计算总数，提前初始化，避免扩容，不过可能出现溢出的情况。 */
    List<String> sequences = new ArrayList<>();
    char[] values = new char[sequenceLen];
    Arrays.fill(values, '0');
    helper(0, oneNumber, values, 0, sequences);
    return sequences;
}

private static void helper(int oneCount, int oneNumber, char[] values, int pos, List<String> sequences) {
    if (oneNumber - oneCount > values.length - pos) {
        return;
    }
    if (oneCount == oneNumber) {
        sequences.add(new String(values));
        return;
    }
    values[pos] = '1';
    helper(oneCount + 1, oneNumber, values, pos + 1, sequences);
    values[pos] = '0';
    helper(oneCount, oneNumber, values, pos + 1, sequences);
}

2、针对零和一的数量和小于等于 64 的优化版本

public static String[] solution1(int zeroNumber, int oneNumber) {
    final int sequenceLen = zeroNumber + oneNumber;
    if ((zeroNumber | oneNumber) < 0 || sequenceLen > 64) {
        throw new IllegalArgumentException(String.format("The number of zero or one are abnormal : zero = %s, one = %s.", zeroNumber, oneNumber));
    }
    if (sequenceLen == zeroNumber || sequenceLen == oneNumber) {
        String sequence = new String(IntStream.range(0, sequenceLen).map(i -> zeroNumber == 0 ? '1' : '0').toArray(), 0, sequenceLen);
        return new String[]{sequence};
    }
    final int resultNumber = (int) MathUtils.nchoosek(sequenceLen, oneNumber);
    long[][] binaryValues = new long[resultNumber][2];
    /* 索引 0 记录二进制值，索引 1 记录 1 的数量 */
    binaryValues[0] = new long[]{0, 0};
    binaryValues[1] = new long[]{1, 1};
    for (int i = 1, count = 2; i < sequenceLen; ++i) {
        int index = count;
        for (int j = 0; j < count; ++j) {
            long value = binaryValues[j][0];
            long oneCount = binaryValues[j][1];
            if (oneCount == oneNumber) {
                continue;
            }
            if (oneNumber - oneCount == sequenceLen - i) {
                binaryValues[j][0] = value | (1L << i);
                binaryValues[j][1] = oneCount + 1;
                continue;
            }
            binaryValues[index++] = new long[]{value | (1L << i), oneCount + 1};
        }
        count = index;
    }
    String[] result = new String[resultNumber];
    for (int i = 0; i < resultNumber; ++i) {
        /* 简单转换 long 数值为二进制字符串 */
        char[] chars = new char[(int) sequenceLen];
        for (int j = 0; j < sequenceLen; ++j) {
            chars[j] = (char) (((binaryValues[i][0] >>> j) & 1) + '0');
        }
        result[i] = new String(chars);
        binaryValues[i] = null;
    }
    return result;
}