4

任意の数の順序付きリストが与えられた場合

List<int> list1 = new List<int> {1, 1, 2};
List<int> list2 = new List<int> {1, 2, 3, 4};
List<int> list3 = new List<int> {1, 2};
List<int> listN = new List<int> {....,....};

各組み合わせの合計が昇順になるように、リストの組み合わせを見つけたいです。例えば、

{1, 1, 1} = 3, where {1 (1st element of list1), 1 (1st element of list2), 1 (1st element of list3)} 
{1, 1, 1} = 3, where {1 (2nd element of list1), 1 (1st element of list2, 1 (1st element of list3)}
{1, 2, 1} = 4
{1, 1, 2} = 4
{2, 1, 1} = 4
...

合計を昇順で求める理由は、最初の M 個の組み合わせ (たとえば、上記の M = 5) だけを計算できるようにするためです。

私の現在の考えは、 List<List<int>> の組み合わせ で説明したように、現在の要素と次の要素の差が 0 であるリストの小さなサブセットから始めることで、すべてのリストの組み合わせを見つけることを何とか拡張することです。

List<int> tempList1 = new List<int> {1, 1};
List<int> tempList2 = new List<int> {1};
List<int> tempList3 = new List<int> {1};

すべての組み合わせを見つけてから、差が最も小さい次の要素をリストに追加します

List<int> tempList1 = new List<int> {1, 1, 2};
List<int> tempList2 = new List<int> {1, 2};
List<int> tempList3 = new List<int> {1, 2};

そこからソリューションセットを構築します。

これは可能ですか、これを行うためのより良い方法はありますか?

4

2 に答える 2

0

単一のアイテムを計算するのは費用がかかりませんが、アイテムの数が多い場合は、すべての結果をメモリに保持して注文することが必要になる場合があります。しかし、私がそれを正しく理解していれば、組み合わせの計算はタスクを解決するのにあまり役立たないようです。

編集：私が応答を書き始めたとき、私は組み合わせについての説明を見ませんでした。いずれにせよ、さまざまな組み合わせのジェネレーターがある場合は、次のアルゴリズムも使用できます。必要な合計のみを生成する一般的なソリューションがあるかどうかはわかりません。

Nがアイテムの数であり、Mが取得したい結果の数であるとしましょう。以下の意味を理解するために、私はN >> Mと仮定します（例えば、はるかに大きい）。

次に、次のアルゴリズムを使用します。

  • 最大M個のアイテムを保持するための結果リストを作成します。
  • N個のアイテムすべてに目を通します。
    • 各アイテムについて、合計を計算します
    • 順序が正しくなるように結果リストに合計を挿入します（バイナリ検索は、おそらくそれを行うために使用する優れたアルゴリズムになります）
    • 挿入後、結果リストをMアイテム以下にトリミングします（挿入されたアイテム、または以前に挿入されたアイテムは、計算結果に応じて除外されます）
  • これで、上位M個のアイテムが降順で表示されます。

そうすることで、元のN個のアイテムの順序に関して上記のアルゴリズムを簡単に安定させることができることに注意してください。

于 2012-12-21T17:06:45.380 に答える
0

これを試して：

List<int> list1 = new List<int> { 1, 1, 2 };
List<int> list2 = new List<int> { 1, 2, 3, 4 };
List<int> list3 = new List<int> { 1, 2 };

var combinations = list1
    .SelectMany(x => list2, (a, b) => new { a, b })
    .SelectMany(x => list3, (combined, c) => new { a = combined.a, b = combined.b, c })
    .Select(comb => new{ Sum = comb.a + comb.b + comb.c, Combination = new List<int>{comb.a, comb.b, comb.c}})
    .OrderBy(summed => summed.Sum);

╔═════════════╦═════╗
║ Combination ║ Sum ║
╠═════════════╬═════╣
║ 1,1,1       ║   3 ║
║ 1,1,1       ║   3 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
╚═════════════╩═════╝

編集：少しクリーンアップ

于 2012-12-21T17:14:39.063 に答える