1

我正在寻找一种方法来获取列表项的所有组合。我想的是有一个二维数组，类似于位图，例如 bit[][] mybitmap;

例如，如果我的列表“A、B、C、D”中有 4 个项目，我希望我的位图像这样填充

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 个，刚刚确认）

谢谢

4

3 回答 3

2

所以......只需从 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-25T07:38:23.943 回答
1

同意马克·格拉维尔的观点。你不能假装生成一个你描述的列表，然后收集你需要的元素。我一直在做类似的事情，但我只需要所有组合的一个子集，所以我在列表生成过程中过滤了我的元素。这样，每次递归迭代（我使用 F#）都不会创建我已经知道的元素，这些元素将在最后被丢弃。

使用这种方法，我可以执行 200 个元素的变化并获得有效结果列表（我已经知道它不会那么大......）

如果您有兴趣，您所描述的问题是一个组合问题。C#这里有一篇不错的文章

于 2011-05-25T07:49:51.810 回答
0

我相信您不需要将所有组合存储在内存中。只需从所有零位的数组（第一个组合）开始。要获得下一个组合，只需将前一个组合的最后一位加 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-25T08:12:01.540 回答