树算法c#实现

本文关键字：实现 算法 | 更新日期: 2023-09-27 17:54:07

我有一些问题，用于解决从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是一个带有一些值的简单名称枚举。

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

我已经尝试了简单的嵌套迭代使用每个列表的foreach，正如预期的那样，需要eons来运行!

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

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

(MyEnumOne, MyEnumOne, MyEnumFour, MyEnumFive, MyEnumTwo)

和，作为这个组合，可以出现几次(MyEnumOne值可以在listOne上多次出现，等等)，我也必须记录这个组合发生了多少次。

树算法c#实现

使用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在他的帖子中所示。

查询中所有中间的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
                };

一般来说，对于这样的问题，您应该尝试构造解决方案，而不是盲目地遍历整个搜索空间寻找它们。

我假设你真正需要做的是:你有N个列表，每个列表有L(i)个元素。-你想生成长度为N的所有组合，其中第一个元素来自第一个列表，第二个元素来自第二个列表，依此类推

似乎没有任何方法可以避免以困难的方式生成所有的组合。所有100个元素^ N ~ 10^14…这要花很长时间

我同意小样本的要求和需要满足的条件。

相关文章：