OCaml: перестановка каждого значения в двух наборах? (как перевести это с Java)

У меня есть два набора, возвращаемые Set.Make(t). Я хотел бы создать все возможные комбинации значений в двух. Как я могу это сделать?

Это работает для создания некоторых пар, но не всех:

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

Это сделало бы это на Java:

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

java permutation ocaml
person Nick Heiner    schedule 02.10.2009    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Если xs и ys — два списка, то их декартово произведение (возвращающее список пар) можно вычислить следующим образом:

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

В этом случае ваши xs и ys это IntSet.elements odp и IntSet.elements ftw

person newacct    schedule 02.10.2009

arrow_upward
6
arrow_downward

Объединение решения @David Crawshaw (с хвостовой рекурсией) с решением @newacct (полностью универсальное):

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)

Это изменит естественный порядок. Его можно восстановить, применив к результату List.rev (List.rev тоже хвостовая рекурсия).

person Chris Conway    schedule 02.10.2009
comment
это не проверка типа: Ошибка: это выражение имеет тип 'a -› ('b * 'a) list -› ('b * 'a) list, но здесь используется с типом 'a -› ('b * ' а) список -> 'а - person Nick Heiner; 03.10.2009

arrow_upward
3
arrow_downward

Вы ищете декартово произведение двух множеств.

Этот вопрос задан в теме в списке рассылки OCaml. Этот ответ предлагает Брайан Херт: Для

module TypeSet = Set.Make(Type);;

Создайте, чтобы представить продукт:

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

Затем создайте продукт с помощью:

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
;;
person David Crawshaw    schedule 02.10.2009