как вычислить растровое изображение?

Question

Я ищу способ получить все комбинации элемента списка. я думаю иметь двумерный массив, похожий на немного карты например, 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, только что подтверждено)

Спасибо

Answer 1

Итак ... просто посчитайте от 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();
}

Answer 2

Согласен с Марком Гравеллом. Вы не можете притворяться, что создали список, подобный тому, который вы описали, а затем собрали нужные вам элементы. Я делал что-то похожее, но мне нужно было только подмножество всех комбинаций, поэтому я фильтровал свои элементы в процессе генерации списка. Таким образом, каждая рекурсивная итерация (я использовал F #) не создает элементы, которые я уже знаю, которые будут отброшены в конце.

При таком подходе я мог бы выполнить вариации 200 элементов и получить список допустимых результатов (который я уже знал, что он будет не таким большим ...)

Если вам интересно, описываемая вами проблема является комбинаторной. Есть хорошая статья на C # здесь

Answer 3

Полагаю, вам не нужно хранить все комбинации в памяти. Просто начните с массива со всеми нулевыми битами (первая комбинация). Чтобы получить следующую комбинацию, просто добавьте 1 к последнему биту предыдущей комбинации (это легко реализующая операция). И так далее. Низкое использование памяти, поддержка до 2 миллиардов цифр. :)

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