2

更新: @bphelpsjr の回答は、私が探しているものを提供します。残念ながら、誰かが彼に反対票を投じましたが、私には賛成票を投じる担当者がいません。私は彼の反応を答えとしてマークしています。

これは非常に長くなりましたが、できるだけ詳細を提供したかったのです。

基本的に、一連のデータを取得し、ルール (以下で定義) に基づいてリストのリストを生成したいと考えています。これは基本的に、パワーセットのフィルター処理されたバージョンです。

次に、これらの結果を繰り返し使用するために保存し (レインボー テーブルの場合と同様)、同じ が常に計算されるのを回避しNます。次に、他のロジックを適用する前に、変数置換 (たとえば、A = 18、B = 30) を使用します (以下では説明しません。私の質問には必要ありません)。

ソリューションを作成するために実験した 2 つの入力オプションを次に示します。文字の代わりに数字を使用することもできます。

入力オプション #1

var completeList = new List<Item>
        {
            new Item('A', 'A'),
            new Item('A', 'B'),
            new Item('A', 'C'),
            new Item('A', 'D'),            
            new Item('B', 'B'),
            new Item('B', 'C'),
            new Item('B', 'D'),           
            new Item('C', 'C'),
            new Item('C', 'D'),            
            new Item('D', 'D')
        };

入力オプション #2

List<Item> aList = new List<Item> 
{
        new Item('A', 'A'),
        new Item('A', 'B'),
        new Item('A', 'C'),
        new Item('A', 'D'),            
    };

    List<Item> bList = new List<Item> 
    {
        new Item('B', 'B'),
        new Item('B', 'C'),
        new Item('B', 'D'),           
    };

    List<Item> cList = new List<Item> 
    {
        new Item('C', 'C'),
        new Item('C', 'D'),            
    };

    List<Item> dList = new List<Item> 
    {
        new Item('D', 'D')
    };

望ましい出力

AA BB CC DD
AA BB CD
AA BC    DD
AA BD CC
AB    CC DD 
AB    CD
AC BB    DD
AC BD
AD BB CC
AD BC

ルール

最初の 3 つは決定的なルールですが、4 番目はもっと欲求です。

  1. ソリューションは、 N個の個別の文字と項目のリストを処理できなければなりません

  2. すべての個別の文字は、アイテムのリストに少なくとも 1 回表示される必要があります。例：

    AA BB CC DD <-- 有効

    AA BB CC <-- 無効、D を含まない

  3. 文字は、特定のアイテム内でのみ繰り返すことができます。例：

    AA BB CC DD <-- 有効

    AA BA CC DD <-- 無効、A は別の項目で繰り返されます

  4. 実行する反復回数を減らすために、ロジックにはできるだけ多くの「アグレッシブ フィルタリング」とショート サーキットを含める必要があります。私は機能する左シフト ソリューションを持っていましたが、(私の?) フィルタリングと短絡を組み込むことができないため、まったく拡張できません。これにより、基本的に、パワーセット全体を反復処理することになりました。

    • 例: 可能性のあるリストの項目に既に含まれている文字が見つかったら、これは無効であるため、次の可能性のある組み合わせに進みます。

    • 例: アイテムの有効なリストが見つかったら、次のラウンドを開始します。

次の 2 つは、各項目の最初の文字でグループ化されたデータ セットを現在持っている方法に基づく潜在的な例です。作成するソリューションの種類によっては、適用できない場合があります。

  • 考えられる例: 項目に次のリストの項目にある文字が含まれている場合、そのリスト全体をスキップして次の項目のリストに移動します。

    AA BC DD <-- C リストは BC でカバ​​ーされているためスキップできます

  • 潜在的な例: リストの潜在的な候補を使い果たしたら (たとえば、最後のリストには 1 つのアイテムしかない)、(私の考えが正しければ) 上のリスト + 1 がアイテムを変更するまで、そのリストを再度必要とするべきではありません。 .

    AA BB CC DD <-- これを見つけたら、BC (DD + 1 の上のリスト) に到達するまで、DD を含むリストの検索を停止します。

    AA BB CD

    AA BC DD <-- また DD が必要

    1. 項目の順序に関係なく、項目のリストが繰り返されることはありません。例：

    AA BB CC DD == BB AA DD CC なので、BB AA DD CC は含めないでください。

私が行った仮定：

  • 最初の開始文字でセットをグループ化する方が簡単です (以下のサンプル データを参照)。これが最適なアプローチでなくても問題ありません。

以下は、便宜上、データを保持するために使用する Item クラスです。

public class Item
{
    public char First { get; set; }
    public char Second { get; set; }

    public Item(char first, char second)
    {
        First = first;
        Second = second;

    public List<char> DistinctCharacters()
    {
        return First == Second ? new List<char> { First } : new List<char> { First,  Second };
    }
}
4

3 に答える 3

0

コメントするのに十分な担当者がいないため、不完全な回答を投稿しています。私は解決策を持っていますが、それを洗練していません。現在、不完全な組み合わせ (AD CC など) を吐き出しており、役に立たないリストを見ないように剪定を行うことができます。

私のアプローチは再帰的ですが、ソリューションを保存することで一部の計算を回避します。たとえば、C のリストを見て、A と B の文字を使用したときに残っている組み合わせは、それまでの組み合わせが AA BB であっても AB であっても同じです。

Memorize()メソッドとメソッドは実装していませんIKnowThis()が、ハッシュテーブルを使用すると簡単なはずです。

foreach (var combo in GenerateCombinations("", 0))   
{
    Console.WriteLine(combo);
}

private static List<string> GenerateCombinations(string used, int listIndex)
    {
        if (listIndex >= _allLists.Count || used.Length == _allLists.Count)
            return new List<string>();

        List<string> combos;

        if (!IKnowThis(used, listIndex, out combos))
        {
            if (used.Contains(_allLists[listIndex][0].First))
                return GenerateCombinations(used, listIndex + 1);

            combos = new List<string>();

            foreach (var item in _allLists[listIndex])
            {
                var newcombos = new List<string>();



                string newUsed = Combine(used, item);
                newcombos.AddRange(GenerateCombinations(newUsed, listIndex + 1));

                if (!used.Contains(item.Second) && !used.Contains(item.First))
                {
                    if (newcombos.Count == 0)
                    {
                        newcombos.Add(item.ToString());
                    }
                    else
                    {
                        for (int i = 0; i < newcombos.Count; i++)
                        {
                            newcombos[i] = item + " " + newcombos[i];
                        }
                    }
                }

                combos.AddRange(newcombos);
            }
        }

        Memorize(used, combos);
        return combos;
    }

    private static string Combine(string used, Item item)
    {
        if (!used.Contains(item.First))
            used += item.First;
        if (!used.Contains(item.Second))
            used += item.Second;

        return used;
    }        
}

public class Item
{
    public char First { get; set; }
    public char Second { get; set; }

    public Item(char first, char second)
    {
        First = first;
        Second = second;
    }
    public string DistinctCharacters()
    {
        return First == Second ? First.ToString() : this.ToString();
    }

    public override string ToString()
    {
        return First.ToString() + Second;
    }
}
于 2014-03-27T18:56:36.100 に答える