how to compute a bitmap?

Question

I am looking for a way to get all combination of a list item. what i thinking is to have a two dimention array, similary to a bit map e.g bit[][] mybitmap;

for example if i have 4 item in my list "A, B, C, D" i want my bitmap to be populate like this

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

but how can i write some C# code to populate my bit map? (PS: my list might have items around 80 to 90, not 100 to 200, just confirmed)

Thanks

Answer 1

I believe you don't need to store all combinations in memory. Just start from array with all zero bits (first combination). To get next combination just add 1 to last bit of previous combination (it is easily implementing operation). And so on. Low memory usage, support of up to 2 billions of digits. :)

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

Answer 2

So... just count from 1 to 15 (=(2^n)-1), and write as binary, perhaps using shift operations.

This is sane for small numbers... but gets rather large quite quickly. For 64 items you can model in a long, but that is 18,446,744,073,709,551,615 combinations... hint: you are never, ever, ever going to loop that far.

For small cases:

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

Answer 3

Agree with Marc Gravell. You cannot pretend to generate a list like the one you describe and then collect the elements you need. I've been doing something similar, but I only needed a subset of all the combinations, so I was filtering my elements during the list generation process. This way, each recursive iteration (I was using F#) does not create the elements that I already know that will be discarded at the end.

With this approach I could perform variations of 200 elements and get the list of valid results (which I already knew it was going to be not so big...)

In case you are interested, the problem you are describing is a combinatory problem. There's a nice article in C# here