生成具有N + 1的

Question

可能重複的隨機位集合：
Randomly pick k bits out of n from a Java BitSet

有一種簡單的方法來生成大小N * N的隨機位集合（如64）和恰好n （公式8）個數是1的隨機順序？

我想過的是，我可能會生成一個隨機位集並檢查bitSet.cardinality（）是否爲8，如果不是，則再試一次，但這似乎是一個性能不佳的解決方案。

任何人有更好的主意嗎？

Answer 1

使用reservoir sampling，這可以在O（n）的時間來完成：

public static BitSet randomBitSet(int size, int cardinality, Random rnd) { 
    if (0 > cardinality || cardinality > size) throw new IllegalArgumentException(); 
    BitSet result = new BitSet(size); 
    int[] chosen = new int[cardinality]; 
    int i; 
    for (i = 0; i < cardinality; ++ i) { 
     chosen[i] = i; 
     result.set(i); 
    } 
    for (; i < size; ++ i) { 
     int j = rnd.nextInt(i+1); 
     if (j < cardinality) { 
      result.clear(chosen[j]); 
      result.set(i); 
      chosen[j] = i; 
     } 
    } 
    return result; 
} 

Answer 2

獲得0到63之間的8件不同的隨機數爲1

設置這些位你的方法並不能保證準確8 1S，每個64位8個1S的只是一個平均值（如果重複足夠的時間） 。

Answer 3

創建您想要選擇的數字列表，例如從0到63.

隨機清單。

將第一個n位設置爲1，例如1。第一個8.

這將有一個O（n^2）時間複雜度。

---

另一種方法是創建一個位集合，並保持設定隨機清除位，直到你在總集8。您不需要測試基數。

int n = ... 
Random rand = new Random(); 
BitSet bs = new BitSet(n * n); 
for(int i = 0; i < n; i++) { 
    int j = rand.nextInt(n * n); 
    if (bs.get(j)) 
     i--; 
    else 
     bs.set(j); 
} 

這通常是，比爲O（n）

Answer 4

1. 設置字符數組略差：{1 1 1 1 1 1 1 1 0 0 ... 0 0 0}正確的數字是1和0。

2. 使用Fisher-Yates算法對字符數組進行隨機洗牌。

3. 將shuffled數組轉換爲BitSet。無論出現「1」字符，都將相應的位設置爲0b1。所有其他位可以設置爲0b0。

ETA：再想一想，你可以直接創建並隨機播放BitSet。底層算法仍然是一樣的。