1

我有一个问题，我必须在嵌套哈希集中找到多个子集组合。基本上我有一个“主”嵌套哈希集，并且从“可能”嵌套哈希集的集合中，我必须以编程方式找到可能是“主”的同时子集的“可能”。

可以说我有以下内容：

            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"}} 不会是子集

基本上每个子集都需要是 master 中相应子集的子集。

4

2 回答 2

1

使用蛮力：

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"}}情况（以及更多）。

于 2010-07-06T19:48:45.643 回答
0

尽可能使用最简单的解决方案。

请记住，如果其他人必须查看您的代码，他们应该能够以尽可能少的努力理解它在做什么。我已经发现很难从您的描述中理解您想要做什么，而且我还没有阅读代码。

如果你发现它工作后太慢了，那就优化它。

如果可能，编写单元测试。单元测试将确保您的优化解决方案也正常工作，并将帮助其他人确保他们的更改不会破坏任何东西。

于 2010-07-06T19:01:02.740 回答