OCaml: permutazione di ogni valore in due set? (Come tradurre questo da Java)

Question

Ho due set, restituiti da Set.Make (t). Vorrei generare ogni possibile combinazione di valori nella due. Come posso fare questo?

Questo funziona per generare alcune coppie, ma non tutti:

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

Questo lo farebbe in Java:

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

Answer 1

Se xs e ys sono due liste, allora il loro prodotto cartesiano (restituzione di un elenco di coppie) può essere calcolato come segue:

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

In questo caso il vostro xs e ys sono IntSet.elements odp e IntSet.elements ftw

Answer 2

Combinando soluzione @ David Crawshaw (che è ricorsiva in coda) con @ di newacct (che è completamente generico):

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)

Questo invertirà l'ordine naturale. Esso può essere recuperato applicando List.rev al risultato (List.rev è anche ricorsiva in coda).

Answer 3

Stai cercando il prodotto cartesiano di due insiemi.

Questa domanda è stato chiesto in un discussione sulla mailing list OCaml. Questa risposta è offerto da Brian Hurt : Per

module TypeSet = Set.Make(Type);;

Crea, per rappresentare il prodotto:

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

Quindi generare il prodotto:

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