3

I'm not able to find an effective way to pick out all permutations of 4 elements from a list of 9 elements in Haskell. The python-way to do the same thing:

itertools.permutations(range(9+1),4)

An not so effective way to do it in Haskell:

nub . (map (take 4)) . permutations $ [1..9]

I would like to find something like:

permutations 4 [1..9]
SlimJim
  • 2,264
  • 2
  • 22
  • 25
  • 1
    here is a similar SO question which can address this problem: http://stackoverflow.com/questions/9831374/euler-43-is-there-a-monad-to-help-write-this-list-comprehension – ErikR Aug 01 '12 at 20:06
  • @user5402 sorry I'm not that hax at Haskell (yet), I can't really see the resemblance. – SlimJim Aug 02 '12 at 07:16

4 Answers4

5

Here is my solution:

import Control.Arrow

select :: [a] -> [(a, [a])]
select [] = []
select (x:xs) = (x, xs) : map (second (x:)) (select xs)

perms :: Int -> [a] -> [[a]]
perms 0 _  = [[]]
perms n xs = do
    (y, ys) <- select xs
    fmap (y:) (perms (n - 1) ys)

It's very lazy and even works for infinite lists, although the output there is not very useful. I didn't bother implementing diagonalization or something like that. For finite lists it's fine.

ertes
  • 166
  • 2
  • 4
    Without using `Control.Arrow`, `select` can be written as: `select (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- select xs ]`, with the additional base case: `select [x] = [(x,[])]`. – lbolla Aug 01 '12 at 21:05
  • 1
    @Ibolla: your "additional base case" is already covered by `select [] = []` – newacct Aug 02 '12 at 00:31
  • @newacct: no, my additional base case is `select [x]`, not `select []`. – lbolla Aug 02 '12 at 10:46
  • @Ibolla: but `select [x]` is `select (x:[])`, which by your recursive case becomes `select (x:[]) = (x,[]) : [(y,x:ys) | (y,ys) <- select []]`. Since we already have `select [] = []`, that list comprehension becomes `[]`, so we get `(x,[]) : []`, which is the same as `[(x,[])]` – newacct Aug 02 '12 at 18:21
2
pick :: Int -> [a] -> [[a]]
pick 0 _ = [[]]
pick _ [] = []
pick n (x : xs) = map (x :) (pick (n - 1) xs) ++ pick n xs

perms :: Int -> [a] -> [[a]]
perms n l = pick n l >>= permutations
Rotsor
  • 13,655
  • 6
  • 43
  • 57
1
replicateM 4 [1..9]

Will do this for you, I believe. It's in Control.Monad.

identity
  • 949
  • 6
  • 14
0

How about this

import Data.List (delete)

perms :: (Eq a) => Int -> [a] -> [[a]]
perms 0 _  = [[]]
perms _ [] = [[]]
perms n xs = [ (x:ys) | x <- xs, ys <- perms (n-1) (delete x xs) ]

Basically, it says, a permutation of n elements from a set is, pick any element as the first element of the result, then the rest is a permutation of n-1 elements from the rest of the set. Plus some base cases. Assumes that elements in the list are unique.

amindfv
  • 8,438
  • 5
  • 36
  • 58
newacct
  • 119,665
  • 29
  • 163
  • 224