OCaml: Permutation jeder Wert in zwei Sätzen? (Wie dies von Java zu übersetzen)

Question

Ich habe zwei Sätze, kehrte von Set.Make (t). Ich möchte jede mögliche Kombination der Werte in den beiden erzeugen. Wie kann ich das tun?

Das funktioniert einige Paare zu erzeugen, aber nicht alle:

List.combine (IntSet.elements odp) (IntSet.elements ftw)

Dies würde es in Java tun:

for (int i : ktr) {
     for (int m : mnx) {
       System.out.println(i + ", " + m);
     }
}

Answer 1

Wenn xs und ys sind zwei Listen, dann ihr kartesisches Produkt (eine Liste von Paaren zurückkehrt) kann wie folgt berechnet werden:

List.concat (List.map (fun x -> List.map (fun y -> (x, y))
                                         ys)
                      xs)

In diesem Fall Ihre xs und ys sind IntSet.elements odp und IntSet.elements ftw

Answer 2

Die Kombination @ David Crawshaw-Lösung (die Schwanz-rekursiv) mit @ newacct ist (die vollständig generisch ist):

let cartesian_product xs ys =
  List.fold_left (fun acc x -> 
    List.fold_left (fun acc y -> 
      (x,y) :: acc) 
      acc ys) 
    [] xs

let product = 
  cartesian_product (IntSet.elements odb) (IntSet.elements ftw)

Dies wird die natürliche Reihenfolge umkehren. Es kann durch die Anwendung List.rev auf das Ergebnis zurückgewonnen wird (List.rev ist auch tail-rekursive).

Answer 3

Sie sind für das cartesianischen Produkt von zwei Sätzen suchen.

Diese Frage wurde gefragt in einem Thread auf der OCaml-Mailingliste. Diese Antwort wird angeboten von Brian Hurt : Für

module TypeSet = Set.Make(Type);;

Erstellen, um das Produkt zu repräsentieren:

module TypeType = struct
    type t = Type.t * Type.t;;
    let compare (x1, x2) (y1, y2) =
        let r = Type.compare x1 y1 in
        if r == 0 then
            Type.compare x2 y2
        else
            r
    ;;
end;;

module TypeTypeSet = Set.Make(TypeType);;

Dann das Produkt erzeugt mit:

let cartesian_product s1 s2 =
    let f x y t = TypeTypeSet.add (x, y) t in
    let g x t = TypeSet.fold (f x) s2 t in
    TypeSet.fold g s1 TypeTypeSet.empty
;;