[Haskell-cafe] Combination-lock problem

[Henning Thielemann]

On Tue, 10 Aug 2004, Florian Boehl wrote:

> I'ld like to generate a list (of lists) that contains all combinations
> of natural numbers stored in another list. It should work like a
> combination-lock. E.g.:
>
> [2,2] -> [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]


I have written a similar routine:


{- | Compositional power of a function,
     i.e. apply the function n times to a value. -}
nest :: Int -> (a -> a) -> a -> a
nest 0 _ x = x
nest n f x = f (nest (n-1) f x)

{- | Generate all possibilities to select n elements out of the list x -}
variate :: Int -> [a] -> [[a]]
variate n x = nest n (\y -> concatMap (\z -> map (z:) y) x) [[]]


Prelude> variate 2 ['a','b','c']
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]


(I'm not sure if it is correct to translate the German word "Variationen"
to "variations".)


To make it complete:

{- | Generate list of all permutations of the input list.
     The list is sorted lexicographically. -}
permute :: [a] -> [[a]]
permute [] = [[]]
permute x =
   concatMap (\(y, z:zs) -> map (z:) (permute (y++zs)))
             (init (zip (inits x) (tails x)))