[Haskell-cafe] Re: Permutation with k levels

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