Хитрый алгоритм ... поиск нескольких комбинаций подмножеств во вложенных HashSets?

Question

У меня проблема с поиском нескольких комбинаций подмножеств во вложенных хэш-наборах.По сути, у меня есть «главный» вложенный HashSet, и из коллекции «возможных» вложенных HashSets я должен программно найти «возможные», которые могут быть одновременными подмножествами «главного».

Допустим, у меня естьследующее:

            var master = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B", "C"}),
                        new HashSet<string>( new string[] { "D", "E"}),
                        new HashSet<string>( new string[] { "F"})
                    }
                ); 
            var possible1  = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B", "C"}),
                        new HashSet<string>( new string[] { "F"})
                    }
                 );
            var possible2 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "D", "E"})
                    }
                 ); 
            var possible3 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "F"})
                    }
                 ); 
            var possible4 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "X", "Y", "Z"})
                    }
                ); 
            var possible5 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B" }),
                        new HashSet<string>( new string[] { "D", "E"})
                    }
                ); 

Вывод, который я должен получить из моего алгоритма, должен быть следующим:

Все возможные подмножества комбинации:

possible1 and possible2
possible3 and possible5
possible2 and possible3
possible1
possible2
possible3
possible5

Я пытаюсьвыяснить лучший способ подойти к этому.Есть, конечно, вариант грубой силы, но я пытаюсь избежать этого, если смогу.

Я просто надеюсь, что мой вопрос был достаточно ясен.

РЕДАКТИРОВАТЬ

Для дальнейшего уточнения того, что составляет подмножество, вот несколько примеров, учитываяmaster {{"A", "B", "C"}, {"C", "D", "E", F "}, {" X "," Y "," Z "}}:

• {{"A", "B"} {"C", "D"}} будет подмножеством
• {{"A", "B", "C"}, {" X "," Y "}} будет подмножеством
• {{" A "," B "}, {" A "," B "}} НЕ будет подмножеством
• {{"A", "B", "C", "D"}} НЕ будет подмножеством
• {{"A", "B", "C"},{"C", "D", "X"}} НЕ будут подмножеством

По сути, каждый дочерний набор должен быть подмножеством соответствующего дочернего элемента в мастере.

Answer 1

Используйте bruteforce:

public static int IsCsInMaster(HashSet<string> childSubset, List<HashSet<string>> master, int startIndex)
{
    for (int i = startIndex; i < master.Count; i++)
        if (childSubset.IsSubsetOf(master[i])) return i;

    return -1;
}

public static bool IsChildInMaster(List<HashSet<string>> child, List<HashSet<string>> master)
{
    foreach (var childSubset in child) if (IsCsInMaster(childSubset, master, 0) == -1) return false;

    return true;
}

public static bool IsChildInMasterMulti(List<HashSet<string>> child, List<HashSet<string>> master)
{
    Dictionary<int, int> subsetChecker = new Dictionary<int, int>();
    List<IEnumerable<int>> multiMatches = new List<IEnumerable<int>>();
    int subsetIndex;

    // Check for matching subsets.
    for (int i = 0; i < child.Count; i++)
    {
        subsetIndex = 0;
        List<int> indexes = new List<int>();

        while ((subsetIndex = IsCsInMaster(child[i], master, subsetIndex)) != -1)
        {
            indexes.Add(subsetIndex++);
        }

        if (indexes.Count == 1)
        {
            subsetIndex = indexes[0];
            if (subsetChecker.ContainsKey(subsetIndex)) return false;
            else subsetChecker[subsetIndex] = subsetIndex;
        }
        else
        {
            multiMatches.Add(indexes);
        }
    }

    /*** Check for multi-matching subsets. ***/ //got lazy ;)
    var union = multiMatches.Aggregate((aggr, indexes) => aggr.Union(indexes));

    // Filter the union so only unmatched subset indexes remain.
    List<int> filteredUion = new List<int>();
    foreach (int index in union)
    {
        if (!subsetChecker.ContainsKey(index)) filteredUion.Add(index);
    }

    return (filteredUion.Count >= multiMatches.Count);
}

И в коде:

IsChildInMasterMulti(possible2, master)

Однако код не обрабатывает случай {{"A","B"},{"A","B"}}.Это НАМНОГО сложнее (помечать используемые подмножества в master, возможно, даже отдельные элементы - рекурсивно).

Edit2 : Третий метод также обрабатывает случай {{"A","B"},{"A","B"}} (и более).

Answer 2

Используйте самое простое из возможных решений.

Имейте в виду, что если кто-то еще должен взглянуть на ваш код, он сможет понять, что он делает, с минимальными усилиями. Мне уже было трудно понять из вашего описания, что вы хотите сделать, и мне еще не приходилось читать код.

Если вы обнаружите, что он работает слишком медленно, оптимизируйте его.

Если возможно, напишите модульные тесты. Модульные тесты обеспечат правильную работу вашего оптимизированного решения и помогут другим убедиться, что их изменения ничего не нарушают.