# [Haskell-cafe] Re: Permutation with k levels

DavidA polyomino at f2s.com
Tue Nov 7 11:41:12 EST 2006

What you're trying to do is called permutations with repetition, whereas
permutations (unqualified) usually refers to permutations without repetition
(and that's what the Haskell code you found is doing).

See http://en.wikipedia.org/wiki/Permutations_and_combinations

To get the result you want, take the list of (letter, probability) pairs, and
generate the Cartesian product of k copies of itself.

cartProd 0 xs = [[]]
cartProd k xs = [x:ys | x <- xs, ys <- cartProd (k-1) xs]

The result is all sequences of k (letter,probability) pairs, allowing
repetitions.

Then you just need to unzip and multiply:

(\lps -> let (ls,ps) = unzip lps in (concat ls, product ps))