如何計算位圖？

我正在尋找一種方法來獲取列表項的所有組合。我的想法是有一個二維數組，類似於位圖例如bit [] [] mybitmap;如何計算位圖？

例如，如果我在我的名單4項「A，B，C，d」我希望我的位圖是填充這樣

A B C D 

0, 0, 0, 1 --> D 
0, 0, 1, 0 --> C 
0, 0, 1, 1 --> C, D 
0, 1, 0, 0 --> B 
0, 1, 0, 1 
0, 1, 1, 0 
0, 1, 1, 1 
1, 0, 0, 0 
1, 0, 0, 1 
1, 0, 1, 0 
1, 0, 1, 1 --> A, C, D 
1, 1, 0, 0 
1, 1, 0, 1 
1, 1, 1, 0 
1, 1, 1, 1 --> A, B, C, D

但我怎麼能寫一些C＃代碼填充我的位圖？（PS：我的名單可能有大約80個項目90個，不是100〜200，剛剛確認）

感謝

來源

2011-05-25 jojo

你想枚舉一個200位的整數？這將需要一段時間。你最好有一個計劃，在太陽已經死亡後... – 2011-05-25 07:35:40

@Damien，它是在80到90左右，我剛剛確認.. – jojo 2011-05-25 07:40:04

@Paul，位圖代表A，B，C，D的組合 – jojo 2011-05-25 07:40:28

我相信你不需要在內存中存儲所有組合。從數組開始，全零位（第一組合）。要獲得下一個組合，只需在前一個組合的最後一位加1（這很容易實現操作）。等等。內存使用量低，支持高達20億位數。 :)

private void button1_Click(object sender, EventArgs e) 
    { 
     string[] items = {"A", "B", "C", "D"}; 
     bool[] bits = new bool[items.Length]; 
     for (int i = 0; i < bits.Length; i++) 
     { 
      bits[i] = false; 
     } 
     while (!bits.All(x => x)) 
     { 
      listBox1.Items.Add(string.Join(", ", GetCombination(items, bits))); 
      AddBit(bits, bits.Length - 1); 
     } 
    } 

    public string[] GetCombination(string[] items, bool[] bits) 
    { 
     List<string> combination = new List<string>(); 
     for (int i = 0; i < bits.Length; i++) 
     { 
      if (bits[i]) 
      { 
       combination.Add(items[i]); 
      } 
     } 
     return combination.ToArray(); 
    } 

    private void AddBit(bool[] bits, int pos) 
    { 
     if (pos < 0) 
     { 
      // overflow :) 
      return; 
     } 
     if (bits[pos]) 
     { 
      bits[pos] = false; 
      AddBit(bits, pos - 1); 
     } 
     else 
     { 
      bits[pos] = true; 
     } 
    }

來源

2011-05-25 08:12:01 artplastika

那麼... ...就從1數到15（=（2^N）-1 ），並以二進制形式寫入，也許使用移位操作。

這對於小數目是理智的......但相當快地變得相當大。對於64個項目，你可以模擬一個很長的，但是這是18,446,744,073,709,551,615組合......提示：你永遠不會永遠循環那麼遠。

對於小案例：

int n = 4; 
int max = 1 << n; 
for (long val = 1; val < max; val++) 
{ 
    long mask = 1 << (n - 1); 
    for (int bit = 0; bit < n; bit++) 
    { 
     bool set = (val & mask) != 0; 
     Console.Write(set ? "1 " : "0 "); 
     mask >>= 1; 
    } 
    Console.WriteLine(); 
}

來源

2011-05-25 07:38:23

同意與Marc Gravell。你不能假裝生成一個你所描述的列表，然後收集你需要的元素。我一直在做類似的事情，但我只需要所有組合的一個子集，所以我在列表生成過程中過濾了我的元素。這樣，每次遞歸迭代（我使用F＃）都不會創建我已經知道的元素，而這些元素最終會被丟棄。

用這種方法我可以執行200種元素的變化和取得的有效結果的列表（我已經知道這將是沒有那麼大...）

如果你有興趣，問題你所描述的是一個組合問題。在C＃中有一篇很好的文章＃here

來源

2011-05-25 07:49:51 Haplo

如何計算位圖？

回答

相關問題