c# - 棘手的算法……在嵌套HashSet中找到子集的多个组合吗?

原文 标签 c# algorithm hashset

我有一个问题,我必须在嵌套哈希集中找到多个子集的组合基本上我有一个“master”嵌套散列集,从一个“可能”嵌套散列集的集合中,我必须以编程方式找到可能是“master”的同时子集的“可能”。
假设我有以下几点:

            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

我在想办法解决这个问题。当然,也有暴力的选择,但我尽量避免。
我只希望我的问题足够清楚。
编辑
为了进一步说明什么构成了一个子集,这里有一些例子,给出了主{“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”}不是子集
基本上,每个子集都需要是主控中相应子集的子集。

最佳答案

使用暴力:

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"}}情况(等等)。

相关文章:

java - 如何更正hashCode()方法以正确使用HashSet集合

c# - 在每个循环迭代中创建对象

c - 使用C标准数学库准确计算标准正态分布的CDF

java - 如何在文本文件中检索某些字符串并根据字符串中的元素排序?

algorithm - 设定操作的数据结构

java - Java中的StringStartsWithKeyMap <T>? (如果键开始于entry.key,则匹配)

java - 提高HashSet的速度

c# - C#多线程聊天服务器,处理断开连接

c# - 将KeyVault机密传递到VSTS中的.net core 2 xUnit / MsTest

c# - InitializeComponent()中的C#'System.StackOverflowException'