如何在函数式编程语言中生成具有重复的列表的所有排列？

Question

我正在尝试自学一些函数式编程语言的编程，最近偶然发现了从长度为 n 的列表生成长度为 m 的所有排列的问题，与重复。从数学上讲，这应该导致总共 n^m 种可能的排列，因为每个 m 'slots' 都可以用任何 n 元素填充。但是，我目前拥有的代码没有给我所有的元素：

let rec permuts n list =
  match n, list with
   0, _ -> [[]]
  | _, [] -> []
  | n, h :: t -> (List.map (fun tt -> h::tt) (permuts (n-1) list))
                 @ permuts n t;;

该算法基本上从具有 m 个元素的列表中取出一个元素，将其与其余元素一起放在所有组合的前面，并将结果连接到一个列表中，仅给出 n C m 结果。

例如，permuts 2 [1;2;3] 的输出结果为

[[1;1]; [1;2]; [1;3]; [2;2]; [2;3]; [3;3]]

而我实际上想要

[[1;1]; [1;2]; [1;3]; [2;1]; [2;2]; [2;3]; [3;1]; [3;2]; [3;3]]

-- 共9个元素。如何修复我的代码以便获得我需要的结果？任何指导表示赞赏。

Answer 1

在 Haskell 中，使用列表理解来执行此操作是很自然的：

samples :: Int -> [a] -> [[a]]
samples 0 _ = [[]]
samples n xs =
  [ p : ps
  | p <- xs
  , ps <- samples (n - 1) xs
  ]

Answer 2

在我看来你永远不想在列表的尾部递归，因为你所有的选择都来自整个列表。

@dfeuer 的 Haskell 代码看起来是正确的。请注意，它从不解构列表 xs。它只是在 n.

上递归

您应该能够复制 Haskell 代码，使用 List.map 代替列表理解的前两行，并使用 (n - 1) 代替下一行。

Answer 3

以下是我在 OCaml 中的编写方式：

let perm src =
  let rec extend remaining_count tails =
    match remaining_count with
    | 0 -> tails
    | _ ->
        (* Put an element 'src_elt' taken from all the possible elements 'src'
           in front of each possible tail 'tail' taken from 'tails',
           resulting in 'new_tails'. The elements of 'new_tails' are one
           item longer than the elements of 'tails'. *)
        let new_tails =
          List.fold_left (fun new_tails src_elt ->
            List.fold_left (fun new_tails tail ->
              (src_elt :: tail) :: new_tails
            ) new_tails tails
          ) [] src
        in
        extend (remaining_count - 1) new_tails
  in
  extend (List.length src) [[]]

List.fold_left 调用可能看起来有点吓人，但效果很好。所以练习使用 List.fold_left 是个好主意。同样，Hashtbl.fold 也是常见且惯用的，您可以使用它来收集散列 table.

的键和值

Answer 4

您的错误出现在第二行：

  | n, h :: t -> List.map (fun tt -> h::tt) (permuts (n-1) list)
                 @ permuts n t

确实，用这个分解 n-tuples 的集合，其中 k 个元素作为

的总和

以第一个元素为前缀的 (n-1) 个元组的集合
具有 (k-1) 个元素的 n-tuples 的集合

看三组的基数，明显不匹配

k^n ≠ k^(n-1) + (k-1)^n

问题是第二项不合适。为避免此问题，最好编写几个辅助函数。我建议编写以下三个辅助函数：

val distribute: 'a list -> 'a list -> 'a list list
(** distribute [x_1;...;x_n] y returns [x_1::y;...x_n::y] *)
val distribute_on_all: 'a list -> 'a list list
(** distribute_on_all x [l_1;...;l_n] returns distribute x l_1 @ ... @ distribute x l_n *)
val repeat: int -> ('a -> 'a) -> 'a -> 'a
(** repeat n f x is f(...(f x)...) with f applied n times *)

那么你的函数就是

let power n l = repeat n (distribute_on_all l) [[]]

如何在函数式编程语言中生成具有重复的列表的所有排列？

How do you generate all permutations of a list with repetition in a functional programming language?

ocaml

functional-programming

permutation