Anstecken wieder in einer Haskell-Lösung (es ist nur einfacher zu arbeiten mit faulen Listen, da sie eingebaut sind):
combinations 0 _ = [[]]
combinations k [] = []
combinations k (x:xs) = map (x:) (combinations (k-1) xs) ++ combinations k xs
Die ersten beiden Fälle ergeben sich aus den Eigenschaften von binomial coefficients und insbesondere: n choose 0 = 1
für alle n
einschließlich n=0
(deshalb ist es der erste Fall 0 choose 0
). Der andere ist 0 choose k = 0
. Die dritte Gleichung ist eine exakte Übersetzung der rekursiven Definition von Kombinationen.
Leider, wenn Sie es auf eine unendliche Liste anwenden gibt es eine triviale Lösung:
> take 10 $ combinations 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11],[1,2,12]]
EDIT: OK, so dass wir wirklich wollen, jede Kombination in einer endlichen Anzahl von Schritten Trog gehen. Bei der obigen Version verwenden wir offensichtlich nur den Ausdruck links von ++
, der nur Kombinationen erzeugt, die mit 1 beginnen. Wir können dieses Problem umgehen, indem wir eine interessante Listenzipping-Funktion definieren, die eine Liste erstellt, indem wir abwechselnd den Kopf jedes einzelnen auswählen Argumentlisten (es ist wichtig, im zweiten Argument nicht streng zu sein):
merge [] ys = ys
merge (x:xs) ys = x:merge ys xs
und es verwenden, statt ++
:
combinations k (x:xs) = map (x:) (combinations (k-1) xs) `merge` combinations k xs
können sehen:
> let comb_10_3 = combinations 3 [1..10]
> let comb_inf_3 = combinations 3 [1..]
> take 10 comb_inf_3
[[1,2,3],[2,3,4],[1,3,4],[3,4,5],[1,2,4],[2,4,5],[1,4,5],[4,5,6],[1,2,5],[2,3,5]]
> comb_10_3 `intersect` comb_inf_3 == comb_10_3
True
> last $ combinations 3 [1..10]
[6,8,10]
> elemIndex [6,8,10] $ combinations 3 [1..]
Just 351
Alle 10 choose 3
Kombinationen sind da!
Wenn es faul ist, kann sein Typ nicht sein, eine Liste zurückzugeben. Eine faule Liste sollte genug sein für das, was Sie wollen: http://enfranchisedmind.com/blog/posts/ocaml-lazy-lists-an-introduction/ –
Hallo Pascal. Ich habe das Beispiel in strenger Schreibweise geschrieben, damit es leichter zu lesen ist. Ich möchte, dass es faul ist, ja. Aber meine Frage ist nicht, wie man faule Listen benutzt. Es geht um die spezifische "Wählen" -Funktion. Ich weiß nicht, wie man alle Möglichkeiten der Länge k aus der ursprünglichen Liste wählen kann. – Surikator
Ihre Frage ist klar, und meine Bemerkung war nur auf die Chance, dass Sie verwirrt waren über Faulheit in OCaml (daher in den Kommentaren). Ich bin mir sicher, dass jemand etwas konstruktiver in den Antworten liefern wird. –