-1

私は、利用可能なシナリオをユーザーが有効であると定義したものに「絞り込む」必要があるという問題に本当に苦労しています。以下は、.Net (C#) で解決しようとしている問題の小さな例です。以下に示すレベル/値を考えると、ユーザーは有効な組み合わせがわずかしかないことを選択できますが、下のレベルが、私が示した 5 ではなく 30 ～ 40 レベルのデータであると想像すると、私のジレンマがわかります。有効な組み合わせにたどり着くには、何百万から何十億もの無効な組み合わせを調べる必要があります。レベル内のすべての値が適用される場合と、ユーザーが指定した組み合わせのみが適用される場合があります。

現在のレベル/データの値:

有効な組み合わせは次のとおりです。

*Notice all from level 4 are valid
Receiver -> Sony -> 500 -999 -> Retail
Receiver -> Sony -> 1000 - Up -> Retail

与えられた 5 レベルの情報から期待される結果:

Receiver -> Sony -> 500-999 -> Open -Box -> Retail
Receiver -> Sony -> 500-999 -> New -> Retail
Receiver -> Sony -> 1000-Up -> Open -Box -> Retail
Receiver -> Sony -> 1000-Up -> New -> Retail

私が試したことは小さなセットでパフォーマンスが高いですが、多くのレベルと組み合わせに大きなギャップがあり、レベルに深く入るまで有効な組み合わせを取り除くことができない場合、私は遭遇しています主要なパフォーマンスの問題。私は明らかに問題に間違って取り組んでいません。

問題への取り組みに関するその他の見解や提案は大歓迎です。

4

1 に答える 1

3

入力を N 個の異なるコレクションに解析でき、それぞれが特定のレベルの有効な値を含むと仮定すると、問題は単純にそれらの N 個のコレクションのデカルト積を見つけることです。

Eric Lippertのブログ投稿では、コンパイル時に不明な多数のシーケンスのデカルト積を取得するソリューションの作成について説明しています。その投稿の最後から取られたコードは次のとおりです。

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) => 
      from accseq in accumulator 
      from item in sequence 
      select accseq.Concat(new[] {item})); 
}

入力例でこのコードを使用します。

var validValues = new string[][]{
    new string[] {"Receiver"},
    new string[]  {"Sony"},
    new string[]  {"500 -999","1000 - Up"},
    new string[]  {"Open -Box","New "},
    new string[]  {"Retail"},
};

foreach(var combination in  validValues.CartesianProduct())
    Console.WriteLine(string.Join(" ", combination));

出力を提供します。

レシーバー ソニー 500 -999 オープン -ボックス小売
レシーバー ソニー 500 -999 新品 小売
レシーバー Sony 1000 - アップ オープン -ボックス リテール
レシーバー Sony 1000 - 新しい小売りをアップ
于 2013-08-09T15:56:31.133 に答える