[Haskell-cafe] Re: Permutation with k levels

[DavidA]

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