获取大小为n但只有k个1的所有二进制组合

Question

我想生成所有长度为n的二进制数，但有一个条件：只有k个1。即

例如对于 n = 4, k = 2,（有2个在4中的组合）

1100
1010
1001
0110
0101
0011

我卡住了，不知道如何生成这个。

- Abdiabdisson

---

你至少应该能够想出一个基本的暴力算法。 - Androbin

实际上，Knuth有一种不错的迭代方法，但我没有时间在这里实现它。从设置了最低的k位开始，然后考虑如何找到下一个数字。在每次迭代中，在至少有一个1之后找到最低的0位。设置该最低的0位，然后如果您已经计算超过m个1，则将最低的m-1位设置为1。 - Persixty

Answer 1

使用基本的递归方法打印所有二进制序列，唯一需要做的就是强制执行您的约束条件：

    private static void binSeq(int n, int k, String seq) {
    if (n == 0) {
        System.out.println(seq);
        return;
    }

    if (n > k) {
        binSeq(n - 1, k, seq + "0");
    }

    if (k > 0) {
        binSeq(n - 1, k - 1, seq + "1");
    }
}

- Sagie Levy

Answer 2

这是我对这个算法的非递归实现。由于二进制字符串有2^n种排列方式，我们可以使用for循环来遍历每一个可能的字符串，并检查其中“1”的数量是否等于k：

private static void generate(int n, int k) {
    for (int i = 0; i < Math.pow(2, n); i++) {
        if (Integer.bitCount(i) != k) {
            continue;
        }

        String binary = Integer.toBinaryString(i);

        if (binary.length() < n) {
            System.out.format("%0" + (n - binary.length()) + "d%s\n", 0, binary);
        } else {
            System.out.println(binary);
        }
    }
}

- Jacob G.

Answer 3

一种方法是从数字集合0..n-1中生成所有k个值的组合，并使用这些值来设置输出中对应的位。 此问答解释了如何从n个元素中生成所有k个元素的组合。有了这些组合，使用按位或运算符1 << v[c][i]来产生最终结果，其中v[c][i]表示第c个组合中的第i个数字。

- Sergey Kalinichenko

Answer 4

以下是使用递归作为Java方法的解决方案

public class NumberOfBinaryPatternsSpecificOnes {

    static int[] bitArray = new int[]{0,1}; // kept binary bits in array

    public static void main(String args[])
    {   
        System.out.println("Below are the patterns\n");
        int n = 4;
        int k = 2;
        drawBinaryPattern(n,"",k,0);
    }
    private static void drawBinaryPattern(int n,String seed,int numberOfOnes,int currentCount)
    {
        if(n==0)
        {
            if(currentCount==numberOfOnes){
                System.out.println(seed);
            }
            return;
        }   
        for(int j=0;j<bitArray.length;j++)
        {
            String temp = seed+bitArray[j];
            int currentcountTemp = bitArray[j]==1?(currentCount+1):(currentCount);

            if(currentcountTemp>numberOfOnes)
            {
                return;
            }
            drawBinaryPattern(n-1,temp,numberOfOnes,currentcountTemp);
        }
    }
}

- Anish Kumar

Answer 5

int n = 4, k=2;

    for (int i = 0; i < Math.pow(2,n) ; i++) {
        int a = Integer.bitCount(i);
        if (a == k) System.out.println(Integer.toBinaryString(i));
    }

我认为这是最简单的答案。

- Abdiabdisson