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

Question

所以我试图生成大小为n的所有二进制文件，但条件是只有k 1s。即

为大小为n = 4，K = 2，（有2超过4的组合）

1100 
1010 
1001 
0110 
0101 
0011 

我卡，不能找出如何产生这一点。

Answer 1

一种方法是从n数字集合0,n-1中生成k值的所有组合，并使用这些值设置输出中的相应位。

This Q&A说明如何从n生成k元素的所有组合。有了这些组合，可以使用按位或的1 << v[c][i]来产生最终结果，其中v[c][i]代表i组合编号c中的第几个数字。

Answer 2

用于打印所有二进制序列剩下的就是执行您的约束的基本递归方法：

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"); 
    } 
} 

Answer 3

这里是我的非递归拿到这个算法。因为有二进制字符串的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); 
     } 
    } 
} 

Answer 4

INT N = 4， K = 2;

​​

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