[Haskell-cafe] Permutation with k levels

[Bulat Ziganshin]

Hello Nuno,

Monday, October 30, 2006, 8:45:24 PM, you wrote:

>  What am i coding in specific? I receive a list in the form:
>   
>      -- l1 is a pair of the identifier and the associated probability
>         l1 = [("A",0.6),("B",0.2)]
>   
>  I must return the permutation with k levels; for example:
>   
>      -- permute l k = ...
>      -- should return
>      permute l1 0 = []
>      permute l1 1 = l1
>      permute l2 2 = [("AA",0.64),("AB",0.16),("BA",0.16),("BB",0.04)]
>      permute l3 3 = [("AAA", Pa*Pa*Pa),
> ("AAB",Pa*Pa*Pb),("ABA",...),("ABB",...),("BAA",...),("BAB",...),("BBA",...),("BBB",...)]

this is just a sort of Cartesian Product. but why you need this? if
this is for generation of huffman codes, there is standard algorithm
that generates optimal encoding - and it is named Huffman algorithm

this algorithm just repeats combining of two nodes with least probability
into the node that has summed probability until only one node remains.
this node got empty code, its sons got codes '0' and '1' and so on,
recursively

you can look into zip sources for this algorithm, although it's
implementation there is not ideal



-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com