OCaml: permutazione di ogni valore in due set? (Come tradurre questo da Java)
-
19-09-2019 - |
Domanda
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);
}
}
Soluzione
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
Altri suggerimenti
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).
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
;;