1

リスト項目のすべての組み合わせを取得する方法を探しています。私が考えているのは、bit[][] mybitmap; などのビットマップと同様に、2 次元配列を持つことです。

たとえば、リストに「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# コードを作成するにはどうすればよいでしょうか。(追伸: 私のリストには 100 から 200 ではなく、80 から 90 のアイテムが含まれている可能性があります。確認したばかりです)

ありがとう

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 に答える