Lazy "n wähle k" in OCaml

Question

Als Teil eines größeren Problems der Aufzählung einer Menge, muss ich eine OCaml-Funktion 'Wählen' schreiben, die eine Liste nimmt und als Liste aller möglichen Sequenzen der Größe k ausgibt von Elementen dieser Liste (ohne sich wiederholende Sequenzen, die durch Permutation voneinander erhalten werden können). Die Reihenfolge in der Endliste ist nicht relevant.

Zum Beispiel

choose 2 [1;2;3;4] = [[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]] 

Irgendwelche Ideen?

Ich möchte die ganze Sache zu faul haben, eine faule Liste ausgeben, aber wenn Sie eine strenge Lösung haben, wird das auch sehr nützlich sein.

Answer 1

Hier ist eine strenge und suboptimale Version. Ich hoffe es ist klar. Es vermeidet Duplikate, indem angenommen wird, dass es keine Duplikate in der Eingabeliste gibt, und indem nur Teillisten erzeugt werden, die in der gleichen Reihenfolge wie in der ursprünglichen Liste sind.

Die Längenberechnung könnte faktorisiert werden, indem die Länge l als Argument von choose übergeben wird. Das würde den Code weniger lesbar, aber effizienter machen.

Für die faulen Version, streuen "faul" und "Lazy.force" auf dem Code ...

let rec choose k l = 
    if k = 0 
    then [ [] ] 
    else 
    let len = List.length l in 
    if len < k 
    then [] 
    else if k = len 
    then [ l ] 
    else 
     match l with 
     h :: t -> 
      let starting_with_h = 
      (List.map (fun sublist -> h :: sublist) (choose (pred k) t)) 
      in 
      let not_starting_with_h = choose k t in 
      starting_with_h @ not_starting_with_h 
     | [] -> assert false 
;; 
    val choose : int -> 'a list -> 'a list list = <fun> 

# choose 3 [1; 2; 3; 4; 5; 6; 7] ;;       
- : int list list = 
[[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 2; 6]; [1; 2; 7]; [1; 3; 4]; [1; 3; 5]; 
[1; 3; 6]; [1; 3; 7]; [1; 4; 5]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7]; 
[1; 6; 7]; [2; 3; 4]; [2; 3; 5]; [2; 3; 6]; [2; 3; 7]; [2; 4; 5]; [2; 4; 6]; 
[2; 4; 7]; [2; 5; 6]; [2; 5; 7]; [2; 6; 7]; [3; 4; 5]; [3; 4; 6]; [3; 4; 7]; 
[3; 5; 6]; [3; 5; 7]; [3; 6; 7]; [4; 5; 6]; [4; 5; 7]; [4; 6; 7]; [5; 6; 7]] 

EDIT:

A lazy_list_append wie unten aus den Kommentaren notwendig erscheint:

type 'a node_t =    
     | Empty 
     | Node of 'a * 'a zlist_t 
and 'a zlist_t = 'a node_t lazy_t 

let rec lazy_list_append l1 l2 = 
    lazy 
    (match Lazy.force l1 with 
     Empty -> Lazy.force l2 
    | Node (h, lt) -> 
    Node (h, lazy_list_append lt l2)) 
;; 

Answer 2

Nur der Vollständigkeit halber stelle ich hier den endgültigen Code, der den strengen Code von Pascal mit meinen faulen Sachen und den nützlichen Bemerkungen aller anderen Pascal zusammenbringt.

Der Lazillus-Listentyp ist definiert, dann zwei Hilfsfunktionen für Lazy (Append und Map) und schließlich die Funktion "Choose", die wir definieren wollen.

type 'a node_t = 
    | Nil            
    | Cons of 'a * 'a t 
and 'a t = ('a node_t) Lazy.t 

let rec append l1 l2 = 
match Lazy.force l1 with 
    | Nil -> l2 
    | Cons (a, l) -> lazy (Cons (a, append l l2)) 

let rec map f ll = lazy (
match Lazy.force ll with 
    | Nil -> Nil 
    | Cons(h,t) -> Cons(f h, map f t)) 

let rec choose k l len = 
    if k = 0 
    then lazy (Cons(lazy Nil,lazy Nil)) 
    else 
     if len < k 
     then lazy Nil 
     else if k = len 
    then lazy (Cons (l,lazy Nil)) 
    else 
     match Lazy.force l with 
      | Cons(h,t) -> let g h sublist = lazy (Cons (h,sublist)) 
          in let starting_with_h = (map (g h) (choose (k-1) t (len-1))) 
          in let not_starting_with_h = choose k t (len-1) 
          in append starting_with_h not_starting_with_h 
      | Nil -> assert false 

Das Ergebnis „wählen k ls n“ Auswertung ist eine faule Liste aller Optionen der k Elemente der Liste ls, mit ls Größe n betrachtet werden. Beachten Sie, dass die Funktion "choose" nicht alle Optionen einer unendlichen Liste abdeckt, wie von Pascal auf Grund der Art der Enumeration hervorgehoben.

Danke, das war wirklich nützlich!

Beste, Surikator.

Answer 3

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!