树算法实现C＃

我有一些问题解决用于找到所有更多钞票组合服用元素的算法选自N diferents列表（其中N> = 2 & &Ñ< = 7 - >这个数目是固定的，我可以使diferent方法为每个N）。存在的问题，就如同：我有五个字典：树算法实现C＃

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上等），我也必须记录这种组合发生了多少次。

来源

2011-05-02 miguel.hpsgaming

你可以定义什么样的组合看起来像你在组合上使用的一些示例逻辑？你能定义所有可能的组合的含义吗？ – mellamokb 2011-05-02 17:11:47

如果该方法是通用的，那么您别无选择，只能检查每个组合，并且需要运行eon。一个短暂但典型的输入 - >输出是必要的。 – 2011-05-02 17:14:42

您可以使用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都将尽快过滤出无效组合。

EDIT

固定溶液有效地计数相同组合多少次发生时，忽略原始源的密钥。

为了实现这一点，我将对每个字典应用一个转换。我将把每个字典转换为一个新的字典，其中键是枚举值，并且该值将是枚举值在原始字典中发生的次数。

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 
       };

来源

2011-05-02 17:50:50 Fede

这几乎解决了我的问题，现在，我该如何满足最后一次编辑的需求，在该解决方案上我需要的解决方案只有不同组合，并且每个解决方案的出现次数是多少？ – 2011-05-03 16:44:50

每个字典的“int”键是否有意义？我的意思是，被允许使用'int'来检查候选解决方案是否有用？可以在返回每个组合之前过滤吗？ – Fede 2011-05-03 17:00:10

这里不需要密钥，可以忽略它，它用于从应用程序中的一个int数组中获取组合。 – 2011-05-03 17:21:51

一般来说，遇到这样的问题，您应该尝试构造的解决方案，而不是盲目地通过整个搜索空间寻找他们。

我假设你真的需要做的是这样的： - 你有N个列表，每个列表都有L（i）个元素。 - 要生成长度为N的所有组合，其中第一个元素来自第一个列表，第二个元素来自第二个列表，依此类推。

似乎没有任何方法可以避免以困难的方式生成所有组合。所有100个元素^ N〜10^14 ...将采取永久。

我第二次请求小样本和需要满足的条件。

来源

2011-05-02 17:29:05 Andrei

树算法实现C＃

回答

相关问题