juedui520
juedui520
采纳率100%
2021-02-27 14:04

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

000000000000000000000000000000000000000000000000000000000000000

111111111111111111111111111111111111111111111111111111111111111

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

例如:

第一组

000000000000000000000000000111111111111111111111111111111111111

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

求大神帮忙。。。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • haiyoushui123456 糖气包 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;
    }
    点赞 1 评论 复制链接分享