[Haskell-cafe] permutations and performance

Henning Thielemann lemming at henning-thielemann.de
Sat Aug 16 15:53:23 EDT 2008


John D. Ramsdell wrote:

> Straight forward permation algorithm.
> 
>> permutations :: Int -> [[Int]]
>> permutations n
>>     | n <=  0 = []
>>     | n == 1 = [[0]]

Btw. I think that case is redundant.

>>     | otherwise =
>>         concatMap (insertAtAllPos (n - 1)) (permutations (n - 1))
>>     where
>>       insertAtAllPos x [] = [[x]]
>>       insertAtAllPos x (y : l) =
>>           (x : y : l) : map (y :) (insertAtAllPos x l)



More information about the Haskell-Cafe mailing list