如何计算位图？

我正在寻找一种方法来获取列表项的所有组合。我的想法是有一个二维数组，类似于位图例如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

如何计算位图？

回答

相关问题