2

誰かが、少なくとも私にとって非常にトリッキーなアルゴリズムを手伝ってくれることを願っています.

問題

結合する必要があるリスト ( )のリスト( 1 <= size <= 5、ただしサイズは実行時まで不明) があります。1 <= size <= 2これが私が見ているものの例です:-

ListOfLists = { {1}, {2,3}, {2,3}, {4}, {2,3} }

だから、私がする必要があることには2つの段階があります:-

(1)。すべての組み合わせが各リストから正確に 1 つの項目を持つように、内部リストを組み合わせる必要があります。つまり、ここでの結果セットで可能な組み合わせは次のようになります。

  • 1,2,2,4,2
  • 1,2,2,4,3
  • 1,2,3,4,2
  • 1,2,3,4,3
  • 1,3,2,4,2
  • 1,3,2,4,3
  • 1,3,3,4,2
  • 1,3,3,4,3

デカルト積がこれを処理するので、ステージ 1 が完了します.....今、ここに私が理解できないひねりがあります-少なくとも私はそれを行う LINQ の方法を理解できません (私はまだLINQ初心者）。

(2)。このデカルト積から重複する結果を除外する必要があります。この場合の重複は、別の行と同じ数の個別のリスト要素を持つ結果セット内の任意の行を構成します。つまり、

1,2,2,4,3 は 1,3,2,4,2 と「同じ」

最初のリスト内の個別の各項目は、両方のリストで同じ回数出現するためです (1 は各リストで 1 回、2 は各リストで 2 回、....

したがって、最終的な結果セットは次のようになります...

  • 1,2,2,4,2
  • 1,2,2,4,3
  • --
  • 1,2,3,4,3
  • --
  • --
  • --
  • 1,3,3,4,3

もう 1 つの例は、ListOfLists が {{2,3}、{2,3}、{2,3}、{2,3}、{2,3} である最悪のシナリオ (組み合わせの観点から) です。 }、つまり、最大サイズの内部リストを含むリスト - この場合、デカルト積の結果セットには明らかに 32 の結果がありますが、取得しようとしているプルーニングされた結果セットは次のようになります。

  • 2,2,2,2,2
  • 2,2,2,2,3 <-- 4 つの 2 と 1 つの 3 (任意の順序) を含む他のすべての結果は抑制されます
  • 2,2,2,3,3 <-- 3 つの 2 と 2 つの 3 を含む他のすべての結果は抑制されます。
  • 2,2,3,3,3
  • 2,3,3,3,3
  • 3,3,3,3,3

そこにいる数学に関心のある人々へ-あなたが助けてくれることを願っています. 私は実際にパート 2 の有効なソリューションを手に入れましたが、これは完全なハックであり、計算量が多いため、プルーニングの問題に対するよりエレガントで効率的な LINQ ソリューションを見つけるためのガイダンスを探しています。

読んでくれてありがとう。

ピップ

これまでに使用したいくつかのリソース (デカルト積を取得するため)

更新 - 解決策

これをすぐに投稿しないことをお詫びします...以下を参照してください

4

3 に答える 3

3

独自に実装してIEqualityComparer<IEnumerable<int>>から、で使用する必要がありますDistinct()。

でのハッシュコードの選択はIEqualityComparer実際のデータによって異なりますが、実際のデータが例のデータに似ている場合は、次のようなもので十分だと思います。

class UnorderedQeuenceComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        return x.OrderBy(i => i).SequenceEqual(y.OrderBy(i => i));
    }

    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(i => i * i);
    }
}

重要な部分は、GetHashCode()O（N）である必要があることです。ソートが遅すぎます。

于 2011-08-04T20:58:25.577 に答える
1 
void Main()
{
    var query =     from a in new int[] { 1 }
                    from b in new int[] { 2, 3 }
                    from c in new int[] { 2, 3 }
                    from d in new int[] { 4 }                   
                    from e in new int[] { 2, 3 }
                    select new int[] { a, b, c, d, e }; 
    query.Distinct(new ArrayComparer());
        //.Dump();
}
 public class ArrayComparer : IEqualityComparer<int[]>
    {
        public bool Equals(int[] x, int[] y)
        {            
            if (x == null || y == null)
                return false;

            return x.OrderBy(i => i).SequenceEqual<int>(y.OrderBy(i => i));

        }

        public int GetHashCode(int[] obj)
        {
            if ( obj == null || obj.Length == 0)
                return 0;
            var hashcode = obj[0];
            for (int i = 1; i < obj.Length; i++)
            {
                hashcode ^= obj[i];
            }
            return hashcode;
        }
    }
于 2011-08-04T21:15:17.433 に答える