Alle Subsets erstellen

Question

Ok. Ich kenne. Dies ist eine Übung von Oderskys Kurs. Aber ich bin tagelang so dran.

Methode definieren alle Teilmengen einer Eingabemenge zu erzeugen:

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

Beispiel: für die Eingabe List(('a', 2), ('b', 2)) Ausgang erhalten:

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

Perfect. Für den Moment bekomme ich zwei verschiedene Dinge: alle Paare (1a) und Liste für einzelnes Element (1b)

1a Es funktioniert. es gibt mir alle Paare (Tupel allgemein)

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

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

1b. Es funktioniert, außer ich leere Liste nicht (natürlich auch ich nicht)

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

    } 

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

Jetzt bin ich total fest, wie beide zu kombinieren. Könnten Sie mir bitte helfen zu verstehen, wie ich das erreichen kann?

Answer 1

Nicht sicher über die Effizienz, aber Sie können einen Blick darauf werfen. Dies ist eine Art Münzwechselproblem, d. H. Bei einer Gesamtmenge an Geld und allen möglichen Münzen, wie viele Wege es gibt, um die Änderung zu bilden. Eine der Ideen (von oben nach unten Ansatz) mit einer rekursiven Funktion zu kommen, die sich gabeln, ob Sie eine bestimmte Art von Münzen nehmen, das ist, was die innere Kombinationsfunktion ist hier tun:

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

Ich kann Ihnen einen Tipp geben, aber ich kann Ihnen keine Lösung geben, da Courrae Ehrenkodex Verletzung wäre.

Beachten Sie, dass es in Ihrer Argumentation gut wäre, (_, 0) als die leere Menge zu betrachten, und dass alle Mengen die leere Menge enthalten! Sie könnten eine Lösung finden, um sie herauszufiltern.

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

Ich hoffe, es wird Ihnen helfen! Viel Glück !