獲取大小爲n的所有二進制組合，但只有k 1s

所以我試圖生成大小爲n的所有二進制文件，但條件是隻有k 1s。即獲取大小爲n的所有二進制組合，但只有k 1s

爲大小爲n = 4，K = 2，（有2超過4的組合）

我卡，不能找出如何產生這一點。

來源

2017-04-11 Abdiabdisson

你應該至少能夠想出一個基本的強力方法 – Androbin

在Knuth中實際上有一個很好的迭代方法，但我沒有時間在這裏實現它。從最低的「k」位開始，然後考慮如何找到下一個數字。在每次迭代中，在至少一個1之後找到最低的0位。設置最低的0位，然後如果你已經計算超過'm'1，則將最低的'm-1'位設置爲1。 – Persixty

一種方法是從n數字集合0,n-1中生成k值的所有組合，並使用這些值設置輸出中的相應位。

This Q&A說明如何從n生成k元素的所有組合。有了這些組合，可以使用按位或的1 << v[c][i]來產生最終結果，其中v[c][i]代表i組合編號c中的第幾個數字。

來源

2017-04-11 20:44:58 dasblinkenlight

用於打印所有二進制序列剩下的就是執行您的約束的基本遞歸方法：

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

來源

2017-04-11 20:53:38

這裏是我的非遞歸拿到這個算法。因爲有二進制字符串的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); 
     } 
    } 
}

來源

2017-04-11 20:56:06

-1

INT N = 4， K = 2;

我認爲這是最簡單的答案。

來源

2017-04-11 21:53:54 Abdiabdisson

獲取大小爲n的所有二進制組合，但只有k 1s

回答

相關問題