Als Teil eines größeren Problems beim Aufzählen einer Menge muss ich eine OCaml-Funktion "choose" schreiben, die eine Liste aufnimmt und als Liste aller möglichen Sequenzen der Größe k aus Elementen dieser Liste ausgibt (ohne sich zu wiederholen) Sequenzen, die durch Permutation voneinander erhalten werden können). Die Reihenfolge in der Endliste ist nicht relevant.
Zum Beispiel
%Vor%Irgendwelche Ideen?
Ich möchte die ganze Sache faul haben und eine faule Liste ausgeben, aber wenn Sie eine strikte Lösung haben, wird das auch sehr nützlich sein.
Hier ist eine strenge und suboptimale Version. Ich hoffe es ist klar. Sie vermeidet Duplikate, indem angenommen wird, dass es keine Duplikate in der Eingabeliste gibt, und indem nur Unterlisten erzeugt werden, die in der gleichen Reihenfolge wie in der ursprünglichen Liste sind.
Die Längenberechnung könnte faktorisiert werden, indem l s Länge als Argument von choose übergeben wird. Das würde den Code weniger lesbar, aber effizienter machen.
Für die faule Version streuen Sie "faul" und "Lazy.force" auf den Code ...
%Vor%BEARBEITEN:
A lazy_list_append , wie es aus den folgenden Kommentaren notwendig erscheint:
Wieder einstecken mit einer Haskell-Lösung (es ist einfacher, mit faulen Listen zu arbeiten, da sie eingebaut sind):
%Vor% Die ersten beiden Fälle ergeben sich aus den Eigenschaften der Binomialkoeffizienten und genauer gesagt: n choose 0 = 1 für alle n einschließlich n=0 (deshalb behandelt es zuerst den Fall 0 choose 0 ). Der andere ist 0 choose k = 0 . Die dritte Gleichung ist die exakte Übersetzung der rekursiven Definition von Kombinationen.
Leider, wenn Sie es auf eine unendliche Liste anwenden, gibt es eine triviale Lösung zurück:
%Vor% BEARBEITEN:
OK, also wollen wir wirklich jede Kombination in einer endlichen Anzahl von Schritten durchlaufen. 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 Listen-Zipping-Funktion definieren, die eine Liste erstellt, indem wir abwechselnd den Kopf jedes einzelnen auswählen seiner Argumentlisten (es ist wichtig, im zweiten Argument nicht strikt zu sein):
und verwenden Sie es anstelle von ++ :
sieht:
%Vor% Alle 10 choose 3 Kombinationen sind da!
Hier ist eine strenge und suboptimale Version. Ich hoffe es ist klar. Sie vermeidet Duplikate, indem angenommen wird, dass es keine Duplikate in der Eingabeliste gibt, und indem nur Unterlisten erzeugt werden, die in der gleichen Reihenfolge wie in der ursprünglichen Liste sind.
Die Längenberechnung könnte faktorisiert werden, indem %code% s Länge als Argument von %code% übergeben wird. Das würde den Code weniger lesbar, aber effizienter machen.
Für die faule Version streuen Sie "faul" und "Lazy.force" auf den Code ...
%Vor%BEARBEITEN:
A %code% , wie es aus den folgenden Kommentaren notwendig erscheint:
%Vor%Wieder einstecken mit einer Haskell-Lösung (es ist einfacher, mit faulen Listen zu arbeiten, da sie eingebaut sind):
%Vor%Die ersten beiden Fälle ergeben sich aus den Eigenschaften der Binomialkoeffizienten und genauer gesagt: %code% für alle %code% einschließlich %code% (deshalb behandelt es zuerst den Fall %code% ). Der andere ist %code% . Die dritte Gleichung ist die exakte Übersetzung der rekursiven Definition von Kombinationen.
Leider, wenn Sie es auf eine unendliche Liste anwenden, gibt es eine triviale Lösung zurück:
%Vor%BEARBEITEN: OK, also wollen wir wirklich jede Kombination in einer endlichen Anzahl von Schritten durchlaufen. Bei der obigen Version verwenden wir offensichtlich nur den Ausdruck links von %code% , der nur Kombinationen erzeugt, die mit 1 beginnen. Wir können dieses Problem umgehen, indem wir eine interessante Listen-Zipping-Funktion definieren, die eine Liste erstellt, indem wir abwechselnd den Kopf jedes einzelnen auswählen seiner Argumentlisten (es ist wichtig, im zweiten Argument nicht strikt zu sein):
%Vor%und verwenden Sie es anstelle von %code% :
%Vor%sieht:
%Vor%Alle %code% Kombinationen sind da!
Als Teil eines größeren Problems beim Aufzählen einer Menge muss ich eine OCaml-Funktion "choose" schreiben, die eine Liste aufnimmt und als Liste aller möglichen Sequenzen der Größe k aus Elementen dieser Liste ausgibt (ohne sich zu wiederholen) Sequenzen, die durch Permutation voneinander erhalten werden können). Die Reihenfolge in der Endliste ist nicht relevant.
Zum Beispiel
%Vor%Irgendwelche Ideen?
Ich möchte die ganze Sache faul haben und eine faule Liste ausgeben, aber wenn Sie eine strikte Lösung haben, wird das auch sehr nützlich sein.
Tags und Links functional-programming ocaml lazy-evaluation list-manipulation