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

Question

I'm trying to self-learn some programming in a functional programming language and recently stumbled on the problem of generating all the permutations of length m from a list of length n, with repetition. Mathematically, this should result in a total of n^m possible permutations, because each of the m 'slots' can be filled with any of the n elements. The code I have currently, however, does not give me all the elements:

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

The algorithm basically takes one element out of a list with m elements, slaps it onto the front of all the combinations with the rest of the elements, and concatenates the results into one list, giving only n C m results.

For example, the output for permuts 2 [1;2;3] yields

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

whereas I actually want

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

-- a total of 9 elements. How do I fix my code so that I get the result I need? Any guidance is appreciated.

AFAIK your example is in OCaml. Why you added haskell and scala tags? — talex, Sep 28 '20 at 09:49
Regarding a Haskell version of what seems to be the N-th power Cartesian product of an input list, you can look at this [closely related SO question](https://stackoverflow.com/a/62765370/11282404). Beware of excessive memory consumption if things are not invoked in the proper order. — jpmarinier, Sep 28 '20 at 10:50
I'm sorry, I am new to this. I added all the tags suggested by the website, but I'm removed the irrelevant ones — , Sep 28 '20 at 11:09

score 1 · Accepted Answer · answered Sep 28 '20 at 20:00

Your error appears on the second line of:

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

Indeed, with this you are decomposing the set of n-tuples with k elements as the sum of

the set of (n-1)-tuples prefixed with the first element
the set of n-tuples with (k-1) elements

Looking at the cardinal of the three sets, there is an obvious mismatch since

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

And the problem is that the second term doesn't fit. To avoid this issue, it is probably better to write a couple of helper function. I would suggest to write the following three helper functions:

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

then your function will be simply

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

score 0 · Answer 2 · answered Sep 28 '20 at 10:16

0

In Haskell, it's very natural to do this using a list comprehension:

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

answered Sep 28 '20 at 10:16

dfeuer

48,079
5
63
167

Thanks for your comment, but I unfortunately cannot follow your list comprehension part. Could you elaborate a bit more, maybe in pseudocode? – Sep 28 '20 at 17:50

score 0 · Answer 3 · answered Sep 28 '20 at 16:54

0

It seems to me you never want to recurse on the tail of the list, since all your selections are from the whole list.

The Haskell code of @dfeuer looks right. Note that it never deconstructs the list xs. It just recurses on n.

You should be able to copy the Haskell code using List.map in place of the first two lines of the list comprehension, and a recursive call with (n - 1) in place of the next line.

answered Sep 28 '20 at 16:54

Jeffrey Scofield

65,646
2
72
108

Thanks for your comment, but I wasn't able to translate @dfeur's suggestion correctly. In particular, could you explain what the first two lines are doing and how it is different from my own map implementation above? – Sep 28 '20 at 17:54
Your map is good. It's the recursion that's not so good. That's what I'm trying to point out, anyway :-) – Jeffrey Scofield Sep 28 '20 at 18:08
I'm sorry, but I think I am indeed recursing on n with the 'permuts (n - 1) list' phrase. I still don't understand why I am not getting all the permutations... – Sep 28 '20 at 18:40

score 0 · Answer 4 · answered Sep 28 '20 at 19:13

Here's how I would write it in 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) [[]]

The List.fold_left calls may look a bit intimidating but they work well. So it's a good idea to practice using List.fold_left. Similarly, Hashtbl.fold is also common and idiomatic, and you'd use it to collect the keys and values of a hash table.

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

4 Answers4