樹算法實現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＃

回答

相關問題