c# - 树算法实现c#

Question

我在解决一个算法时遇到了一些问题，该算法用于从 N 个不同的列表中查找所有可能的组合(其中 N>=2 && N<=7 -> 这个数字是固定的，我可以为每个 N 制定不同的方法) . 问题是这样的: 我有五本词典:

IDictionary<int, MyEnum> listOne; 
IDictionary<int, MyEnum> listTwo;
IDictionary<int, MyEnum> listThree;
IDictionary<int, MyEnum> listFour;
IDictionary<int, MyEnum> listN;

enum MyEnum
    {
    MyEnumOne,
    MyEnumTwo,
    MyEnumThree,
    MyEnumFour,
    MyEnumFive,
    MyEnumOther
   }

可以包含任意数量的元素(不超过 100 个，大多数情况下它们将包含 32 到 64 个元素) 其中 MyEnum 是一个带有一些值的简单名称枚举。

对于每个可能的组合，我都有一些方法来检查组合并检查它是否满足某些条件，如果满足，则根据组合存储一些数据。

我尝试过对每个列表使用 foreachs 进行简单的嵌套迭代，正如预期的那样，需要很长时间才能运行!

任何帮助，例如我应该从哪里开始，我应该做什么，或者我不应该做什么，都将非常受欢迎!如果需要更多信息，请随时询问!

**编辑: 一个组合，基于如前所示的五个列表，例如:

(MyEnumOne, MyEnumOne, MyEnumFour, MyEnumFive, MyEnumTwo)

而且，由于这种组合可以出现多次(因为 MyEnumOne 值可以在 listOne 上出现多次，等等)，我还必须记录这种组合发生了多少次。

Answer 1

您可以使用 LINQ 轻松解决此类问题。

var solutions = from pair1 in listOne
                where IsCandidate(pair1)
                from pair2 in listTwo
                where IsCandidate(pair1, pair2)
                from pair3 in listThree
                where IsCandidate(pair1, pair2, pair3)
                from pair4 in listFour
                where IsCandidate(pair1, pair2, pair3, pair4)
                from pair5 in listFive
                where IsCandidate(pair1, pair2, pair3, pair4, pair5)
                from pair6 in listSix
                where IsCandidate(pair1, pair2, pair3, pair4, pair5, pair6)
                from pair7 in listSeven
                where IsSolution(pair1, pair2, pair3, pair4, pair5, pair6, pair7)
                select new { pair1, pair2, pair3, pair4, pair5, pair6, pair7 };

当然，这种方法之所以有效，只是因为列表的数量在编译时是已知的。另一种方法是使用一种通用方法来构建可能的组合，如 Eric Lippert shows in his post .

查询中所有那些中间的where，都是为了尽快过滤掉无效的组合。

编辑

修复了有效计算相同组合发生次数的解决方案，忽略了原始源的键。

为此，我将对每个字典应用一个转换。我将把每个字典转换成一个新字典，其中键是枚举值，值是枚举值在原始字典中出现的次数。

IDictionary<MyEnum, int> CountOccurrences(IEnumerable<MyEnum> values)
{
    return (from e in values group e by e).ToDictionary(grp => grp.Key, grp => grp.Count());
}

var solutions = from p1 in CountOccurrences(listOne.Values)
                where IsCandidate(p1)
                from p2 in CountOccurrences(listTwo.Values)
                where IsCandidate(p1, p2)
                from p3 in CountOccurrences(listThree.Values)
                where IsCandidate(p1, p2, p3)
                from p4 in CountOccurrences(listFour.Values)
                where IsCandidate(p1, p2, p3, p4)
                from p5 in CountOccurrences(listFive.Values)
                where IsCandidate(p1, p2, p3, p4, p5)
                from p6 in CountOccurrences(listSix.Values)
                where IsCandidate(p1, p2, p3, p4, p5, p6)
                from p7 in CountOccurrences(listSeven.Values)
                where IsSolution(p1, p2, p3, p4, p5, p6, p7)
                select new {
                    E1 = p1.Key,
                    E2 = p2.Key,
                    E3 = p3.Key,
                    E4 = p4.Key,
                    E5 = p5.Key,
                    E6 = p6.Key,
                    E7 = p7.Key,
                    Times = p1.Value * p2.Value * p3.Value * p4.Value * p5.Value * p6.Value * p7.Value
                };