Создать все подмножество

Question

Ok. Я знаю. Это упражнение с курса Одерского. Но я так долго задерживался на этом.

определить метод для создания всех подмножеств входного набора:

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)))

Теперь я полностью застрял, как совместить оба. Не могли бы вы помочь мне понять, как я могу это достичь?

Answer 1

Не уверен в эффективности, но вы можете взглянуть на это. Это своего рода проблема смены монет, т. Е. С учетом общей суммы денег и всех возможных монет, сколько способов внести изменения. Одна из идей (от верхней части к нижней части подхода) грядет с рекурсивной функцией, которая раздвоенный будет ли принимать определенный вид монет, который является то, что внутренняя функция сочетание делает здесь:

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))) 

Answer 2

Я могу дать вам совет, но я не могу дать вам решение, так как было бы нарушением кода чести coursera.

Обратите внимание, что в ваших рассуждениях было бы неплохо рассмотреть (_, 0) как пустой набор и что все наборы содержат пустой набор! Вы могли бы подумать о решении отфильтровать их.

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

Я надеюсь, что это вам поможет! Удачи !