OCaml: permutación de todos los valores de dos conjuntos? (Cómo traducir esto desde Java)

Question

I tienen dos juegos, devuelto por Set.Make (t). Me gustaría para generar todas las combinaciones posibles de los valores en los dos. ¿Cómo puedo hacer esto?

Esto funciona para generar algunas parejas, pero no todos:

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

Esto lo haría en Java:

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

Answer 1

Si xs y ys son dos listas, entonces su producto cartesiano (volviendo una lista de pares) se puede calcular como sigue:

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

En este caso, su xs y ys se IntSet.elements odp y IntSet.elements ftw

Answer 2

La combinación de la solución de @ David Crawshaw (que es recursiva de cola) con @ de newacct (que es totalmente genérico):

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)

Esto invertirá el orden natural. Se puede recuperarse mediante la aplicación de List.rev al resultado (List.rev es también recursiva de cola).

Answer 3

Se busca el producto cartesiano de dos conjuntos.

Esta pregunta se ha hecho en un hilo en la lista de correo OCaml. Esta respuesta es ofrecido por Brian Hurt : Para

module TypeSet = Set.Make(Type);;

Crea, para representar el producto:

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

A continuación, generar el producto con:

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