創建所有子集

好的。我知道。這是來自Odersky課程的練習。但是我很困惑這幾天。創建所有子集

定義方法來創建輸入集合的所有子集：

def combination(occ: List[(Char,Int)]) : List[List[(Char,Int)]]

實施例：用於輸入List(('a', 2), ('b', 2))獲得輸出：

List(
    List(), 
    List(('a', 1)), 
    List(('a', 2)), 
    List(('b', 1)), 
    List(('a', 1), ('b', 1)), 
    List(('a', 2), ('b', 1)), 
    List(('b', 2)), 
    List(('a', 1), ('b', 2)), 
    List(('a', 2), ('b', 2)) 
)

完善。目前，我得到兩件不同的事情：所有夫婦（1a）和單個元素列表（1b）

1a它的工作原理。它給了我所有的夫妻（一般的元組）

def combinations(occurrences: List[(Char,Int)]) : List[List[(Char,Int)]] = { 
    if (occurrences.isEmpty) List(Nil) 
    else { 
     val entry = occurrences.head; 
     for (
      first <- (entry._2 to 1 by -1).toList; 
      rest <- combinations(occurrences.tail)) 
     yield (entry._1, first) :: rest 
    } 
    }

輸出List(List((a,2), (b,2)), List((a,2), (b,1)), List((a,1), (b,2)), List((a,1), (b,1)))

1B。它的工作原理只是我不明白空列表（嗯，當然我不）

def combinations(occurrences: List[(Char,Int)]) : List[List[(Char,Int)]] = { 
    for (entry <- occurrences; 
     freq <- (entry._2 to 1 by -1).toList) yield List((entry._1,freq)) 

    }

輸出List(List((a,2)), List((a,1)), List((b,2)), List((b,1)))

現在我完全陷入如何既結合起來。你能幫我理解我該怎麼做到這一點？

來源

2017-02-21 Antonio Calì

我很討厭告訴你這一點，因爲當我讀完這門課時閱讀這樣的東西會讓我爬上一堵牆，但它可以在一個語句中完成，即'='後面不需要'{' 。這是一個相當長的單一語句（我將它分成3行），涉及遞歸，標準庫中的一些項目以及文件中另一個方法的調用（提示：它是該文件中的下一個方法）。我希望這不是更有害，而不是有益的。祝你好運。 – jwvh

只有標準庫的方法才能提供任何建議？ –

我使用了'::'和'flatMap（）'，並用'distinct'刪除了冗餘。（不要告訴任何人，我這樣說。） – jwvh

不確定效率，但你可以看看這個。這是一種硬幣更換問題，即給定總金額和所有可能的硬幣，有多少種方式來組成這種變化。其中一個想法（從上至下的方法）是拿出其中分叉你是否會採取特定種類的硬幣，這是一個遞歸函數什麼內組合功能在這裏做什麼：

def combinations(occurrences: List[(Char,Int)]) : List[List[(Char,Int)]] = { 
    // total number of coins 
    val tot = occurrences.map(_._2).sum 

    // add a pair to an existing combination 
    def add(counter: List[(Char, Int)], element: (Char, Int)) = { 
     val countMap = counter.toMap 
     (countMap + (element._1 -> (countMap.getOrElse(element._1, 0) + element._2))).toList 
    } 

    // a recursive function to calculate all the combinations 
    def combinations(occurs: List[(Char,Int)], n: Int): List[List[(Char,Int)]] = { 
     if(n == 0) List(List()) 
     else if(occurs.isEmpty) List() 
     else { 
     val firstElement = if(occurs.head._2 == 1) List() else List((occurs.head._1, 1)) 
     // all the combinations if you take the first kind of coin 
     val headComb = combinations(firstElement ++ occurs.tail, n - 1) 

     // all the combinations if you don't take the first kind of coin 
     val tailComb = combinations(occurs.tail, n)  

     // add the first coin pair to head combination and concatenate it with tail combination 
     headComb.map(add(_, (occurs.head._1, 1))) ++ tailComb  
     } 
    } 

    // calculate the combinations for each amount separately 
    (0 to tot).toList.flatMap(combinations(occurrences, _)) 
} 


combinations(List()) 
// res49: List[List[(Char, Int)]] = List(List()) 

combinations(List(('a', 1))) 
// res50: List[List[(Char, Int)]] = List(List(), List((a,1))) 


combinations(List(('a', 1), ('b', 2))) 
// res51: List[List[(Char, Int)]] = List(List(), List((a,1)), List((b,1)), List((b,1), (a,1)), List((b,2)), List((
// b,2), (a,1))) 

combinations(List(('a', 2), ('b', 2))) 
// res52: List[List[(Char, Int)]] = List(List(), List((a,1)), List((b,1)), List((a,2)), List((b,1), (a,1)), List((
// b,2)), List((b,1), (a,2)), List((b,2), (a,1)), List((b,2), (a,2)))

來源

2017-02-22 01:27:04 Psidom

嗯，我很高興它的工作原理，但我不能相信它必須很難實現這樣的東西:(無論如何，我真的很感謝你，會嘗試我的擁有自上而下的不同實現方式 –

我可以給你一個小費，但我不能給你一個解決方案，因爲這將是違反行爲守則代碼侵犯。

請注意，在您的推理中，將(_, 0)作爲空集合，並且所有集合都包含空集合將是一件好事！你可以想出一個解決方案來過濾掉它們。

List(('a', 2), ('b', 2)) <=> List(('a', 2), ('b', 2), ('a', 0), ('b', 0))

我希望它能幫助你！祝你好運！

來源

2017-02-22 01:38:23

使用範圍（entry。_2到1 by -1）自動過濾出是否存在（_，0），因爲生成for映射到None並退出 –

是的，但您不想用0跳過集合，您希望在沒有它的情況下添加它們 –

創建所有子集

回答

相關問題