Ленивый "n выбрать k" в OCaml

В рамках более масштабной задачи перечисления множества мне нужно написать функцию OCaml 'choose', которая берет список и выводит как Список всех возможных последовательностей размера k, составленных из элементов этого списка (без повторения последовательностей, которые могут быть получены друг от друга путем перестановки). Порядок их размещения в конечном списке не имеет значения.

Например, 

choose 2 [1;2;3;4] = [[1;2];[1;3];[1;4];[2;3];[2;4];[3;4]]

Есть идеи?

Я хотел бы иметь все это, чтобы быть ленивым, выводя ленивый список, но если у вас есть строгое решение, которое тоже будет очень полезно.

3 8
functional-programming lazy-evaluation ocaml list-manipulation

3 ответа:

Здесь является строгим и неоптимальный вариант. Надеюсь, это понятно. Он позволяет избежать дублирования, предполагая, что во входном списке нет дубликатов, и генерируя только подсписки, расположенные в том же порядке, что и в исходном списке.

Вычисление длины может быть учтено путем передачи длины l в качестве аргумента choose. Это сделало бы код менее читаемым, но более эффективным.

Для ленивой версии, посыпать "ленивый "и" ленивый.сила " на своем код...

let rec choose k l =
  if k = 0 
  then [ [] ]
  else
    let len = List.length l in
    if len < k
    then []
    else if k = len
    then [ l ]
    else
      match l with
      h :: t ->
          let starting_with_h =
            (List.map (fun sublist -> h :: sublist) (choose (pred k) t))
          in
          let not_starting_with_h = choose k t in
          starting_with_h @ not_starting_with_h
      | [] -> assert false
;;
  val choose : int -> 'a list -> 'a list list = <fun>

# choose 3 [1; 2; 3; 4; 5; 6; 7] ;;                        
- : int list list =
[[1; 2; 3]; [1; 2; 4]; [1; 2; 5]; [1; 2; 6]; [1; 2; 7]; [1; 3; 4]; [1; 3; 5];
 [1; 3; 6]; [1; 3; 7]; [1; 4; 5]; [1; 4; 6]; [1; 4; 7]; [1; 5; 6]; [1; 5; 7];
 [1; 6; 7]; [2; 3; 4]; [2; 3; 5]; [2; 3; 6]; [2; 3; 7]; [2; 4; 5]; [2; 4; 6];
 [2; 4; 7]; [2; 5; 6]; [2; 5; 7]; [2; 6; 7]; [3; 4; 5]; [3; 4; 6]; [3; 4; 7];
 [3; 5; 6]; [3; 5; 7]; [3; 6; 7]; [4; 5; 6]; [4; 5; 7]; [4; 6; 7]; [5; 6; 7]]

Правка:

A lazy_list_append как представляется необходимым из приведенных ниже комментариев: 

type 'a node_t =             
      | Empty
      | Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t

let rec lazy_list_append l1 l2 =
  lazy 
    (match Lazy.force l1 with
      Empty -> Lazy.force l2 
    | Node (h, lt) ->
    Node (h, lazy_list_append lt l2))
;;
9

Снова подключаемся к решению Haskell (просто проще работать с ленивыми списками, так как они встроены): 

combinations 0 _ = [[]]
combinations k [] = []
combinations k (x:xs) = map (x:) (combinations (k-1) xs) ++ combinations k xs
Первые два случая вытекают из свойствбиномиальных коэффициентов и более конкретно: n choose 0 = 1 для всех n, включая n=0 (поэтому сначала нужно обработать случай 0 choose 0). Другой - 0 choose k = 0. Третье уравнение является точным переводом рекурсивного определения комбинаций.

К сожалению, когда вы применяете его к бесконечный список возвращает тривиальное решение: 

> take 10 $ combinations 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11],[1,2,12]]

Править: Итак, мы действительно хотим пройти через каждую комбинацию за конечное число шагов. В приведенной выше версии мы, очевидно, используем только выражение слева от ++, которое генерирует только комбинации, начинающиеся с 1. Мы можем обойти эту проблему, определив интересную функцию сжатия списка, которая строит список, поочередно выбирая заголовок каждого из его списков аргументов (важно быть нестрогим в второй аргумент): 

merge [] ys = ys
merge (x:xs) ys = x:merge ys xs

И использовать его вместо ++: 

combinations k (x:xs) = map (x:) (combinations (k-1) xs) `merge` combinations k xs

Давайте посмотрим: 

> let comb_10_3 = combinations 3 [1..10]
> let comb_inf_3 = combinations 3 [1..]
> take 10 comb_inf_3 
[[1,2,3],[2,3,4],[1,3,4],[3,4,5],[1,2,4],[2,4,5],[1,4,5],[4,5,6],[1,2,5],[2,3,5]]
> comb_10_3 `intersect` comb_inf_3 == comb_10_3 
True
> last $ combinations 3 [1..10]
[6,8,10]
> elemIndex [6,8,10] $ combinations 3 [1..]
Just 351

Все комбинации 10 choose 3 есть!

7

Просто для полноты картины, я помещаю здесь окончательный код, который объединяет строгий код от Pascal с моим ленивым материалом и всеми другими полезными комментариями Паскаля.

Определен тип ленивого списка, затем две вспомогательные ленивые функции (append и map) и, наконец, функция "выбрать", которую мы стремимся определить.

type 'a node_t =
  | Nil                                            
  | Cons of 'a * 'a t
and 'a t = ('a node_t) Lazy.t

let rec append l1 l2 = 
match Lazy.force l1 with
    | Nil -> l2 
    | Cons (a, l) -> lazy (Cons (a, append l l2))

let rec map f ll = lazy (
match Lazy.force ll with
    | Nil ->    Nil
    | Cons(h,t) -> Cons(f h, map f t) )

let rec choose k l len =
  if k = 0 
  then lazy (Cons(lazy Nil,lazy Nil))
  else
        if len < k
        then lazy Nil
        else if k = len
    then lazy (Cons (l,lazy Nil))
    else
      match Lazy.force l with
          | Cons(h,t) ->  let g h sublist = lazy (Cons (h,sublist))
                          in let starting_with_h = (map (g h) (choose (k-1) t (len-1)))
                          in let not_starting_with_h = choose k t (len-1)
                          in append starting_with_h not_starting_with_h
          | Nil -> assert false

Результатом вычисления "choose k ls n" является ленивый список всех вариантов k элементов списка ls, причем ls рассматривается до размера n. заметим, что, как как указывает Паскаль, из-за способа, которым происходит перечисление, функция choose не будет охватывать все варианты бесконечного списка.

Спасибо, это было действительно полезно!

Лучший, Сурикатор.

3