[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))
More information about the Haskell-Cafe
mailing list