2

セットの数字を組み合わせて、セットのサイズを小さくする必要があります。考えられるすべての組み合わせが必要です。これが私の状況を説明するかもしれない2つの例です。

1）Set1には4つのエントリがあり、Set2には2つのエントリがあるため、それぞれ2つの数値を組み合わせる必要があります。

Set1 = {70, 100, 50, 200}; Set2 = {"part1", "part2"}
All combinations I want to retrive should look like following:
"part1"        |"part2"
  70 + 100       |  50 + 200
  70 + 50        | 100 + 200
  70 + 200       |  50 + 100
 100 + 50       |  70 + 200
 100 + 200      |  50 +  70
  50 + 200       | 100 +  70
 50             |  70 + 100 + 200
 70             |  50 + 100 + 200
 100            |  50 +  70 + 200
 200            |  50 +  70 + 100  
 70 + 100 + 200 |  50
 50 + 100 + 200 |  70
 50 +  70 + 200 |  100
 50 +  70 + 100 |  200

2）Set1には4つのエントリがあり、Set2には3つのエントリがあるため、2つの数値を1回だけ組み合わせる必要があります。

Set1 = {70, 100, 50, 200}; Set2 = {"part1", "part2", "part3"}
All combinations I want to retrive should look like following:
"part1"   |"part2"     |"part3"
   70        | 100        |  50 + 200
   70        |  50        | 100 + 200
   70        | 200        |  50 + 100
   50        |  70        | 100 + 200 
   50        | 100        |  70 + 200
   50        | 200        |  70 + 100
 100       |  70        |  50 + 200
 100       | 200        |  50 +  70
 100       |  50        | 200 +  70
 200       |  70        |  50 + 100
 200       | 100        |  50 +  70
 200       |  50        |  70 + 100
   70        |  50 + 200  |  100
   70        | 100 + 200  |   50
   70        |  50 + 100  |  200
   50        | 100 + 200  |   70
   50        | 200 + 70   |  100
   50        |  70 + 100  |  200
 100       |  50 + 200  |   70
 100       |  50 +  70  |  200
 100       | 200 +  70  |   50
 200       |  50 + 100  |   70
 200       |  50 +  70  |  100
 200       |  70 + 100  |   50 
   50 + 200  | 100        |  70
 100 + 200 |  50        |  70
   50 + 100  | 200        |  70
 100 + 200 |  70        |  50
   70 + 200  | 100        |  50
   70 + 100  | 200        |  50
   50 + 200  |  70         | 100
   50 +  70  | 200         | 100
 200 +  70 |  50         | 100
   50 + 100  |  70         | 200
   50 +  70  | 100         | 200
   70 + 100  |  50         | 200

助けてくれてありがとう。私の懸念をよりよく説明する言葉は思いつかない。でも、どんな質問にも喜んでお答えします。あなたの助けを借りて、私は私の質問を立証することができるかもしれません。アプリケーションはC＃で記述されていますが、必ずしもソースコードは必要ありません。私の問題は、実装ではなく概念です。

前もって感謝します！

4

2 に答える 2

0

OK、ここでの一般的な考え方は

  • から始めます{0, 0, 0, 0}-これは、の各要素のゼロですSet1。
  • 0の最初の項目を表しますSet2。したがって、この最初の配列は「のすべてが」Set1の最初の項目に属しSet2ます。
  • これに対応するパーティションを返します。
  • にインクリメント{0, 0, 0, 0}し{0, 0, 0, 1}ます。
  • 1の2番目の項目を表しますSet2。したがって、この配列は「の2番目の項目に属する最後の項目を除いて、のすべてSet1がの最初の項目に属します」です。Set2Set2
  • これに対応するパーティションを返します。
  • にインクリメント{0, 0, 0, 1}します{0, 0, 1, 0}（または{0, 0, 0, 2}に2つ以上のアイテムがある場合Set2）。
  • {1, 1, 1, 1}ヒット（または{2, 2, 2, 2}など）してそれ以上進むことができなくなるまで繰り返します。

次に、「パーティションに空の部分がある場合は、気にしないでください」というロジックを追加できます。

私はこれを次のように実装しました：

static IEnumerable<ILookup<T, U>> Pool<T, U>(T[] t, U[] u)
{
    // Start off with all zeroes.
    int[] indices = new int[u.Length];

    while (true)
    {
        // Build a Lookup from the array.
        var lookup = (Lookup<T,U>)indices
            .Select((ti, ui) => new { U = u[ui], T = t[ti] })
            .ToLookup(p => p.T, p => p.U);
        // Only return it if every part is non-empty.
        if (lookup.Count == t.Length)
            yield return lookup;

        // Increment to the next value.
        int toIncrement = u.Length - 1;
        while (++indices[toIncrement] == t.Length)
        {
            indices[toIncrement] = 0;

            // Stop when we can't increment further.
            if (toIncrement-- == 0)
                yield break;
        }
    }
}

あなたはそれを呼び出すことができます

foreach (var q in Pool(
    new[] { "part1", "part2" },
    new[] { 70, 100, 50, 200 }))
{
    foreach (int i in q["part1"])
        Console.Write(i + " ");
    Console.Write("| ");
    foreach (var ii in q["part2"])
        Console.Write(ii + " ");
    Console.WriteLine();
}

怠惰なためパラメータ配列を作成しましたが、リストにすることも、列挙可能にして呼び出すこともできToArrayます。

于 2013-01-21T14:29:27.533 に答える
0

あなたの問題の主な問題は次のとおりです。

特定のセットのすべてのサブセットを取得する方法は?

これが私の考えです。最初のセットは 32 要素を超えないと思います。そうでなければ、結果は非常に大きくなります。

次に、特定のセットについて、このセットの各サブセットをとMySet = { a, b, c, d, e }の間の値で記述することができます。02^5 - 1

どのように ？

ビットを使って！OK たとえば、数値5(00101バイナリ) を意味しa、cサブセットに含まれます。

Nしたがって、特定の要素セットのサブセットのコレクション全体を取得します。0から2^N-1除外するまで繰り返すだけです。

では、他のパーツ (最後のパーツを除く) を作成するにはどうすればよいでしょうか?

最初のセットの補数を取得し、そのサブセットを反復するだけです。

では、最終回は？

以前のパーツを補完してください!

この手法を使用すると、前のサブセットの補数を探す必要がなくなる可能性がありますが、非標準のビット演算が必要になります。

于 2013-01-21T14:17:34.303 に答える