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