[Haskell-cafe] Re: Permutation with k levels
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).
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
Then you just need to unzip and multiply:
(\lps -> let (ls,ps) = unzip lps in (concat ls, product ps))
More information about the Haskell-Cafe