permutations

Description

This code takes a permutation and creates a list of cycles.

Code

{-

print permutations in cycle notation

-}

import Data.List(permutations,(\\))


-- TODO: redefine * operator

{-

getImage returns y, the image of x, where the mapping from x to y is
expressed as a list of tuples, f.

This function assumes that there is a value corresponding to 'a'.

-}

-- TODO: generalize
--getImage :: [(Int,Int)] -> Int -> Int
{-
getImage f a
given a list of tuples representing a permutation function,
returns the image 


-}

getImage f a = maybe (-1) id $ lookup a f

{-
getChain returns the cycle produced by a with the function f

-}
getCycle f a = [a] ++ (takeWhile (/= a) $ tail $ iterate (getImage f) a)

        
{-               

makeCycles takes a list of integers and a mapping table, f and returns a list of all cycles

-}
               
makeCycles :: [Int]->[(Int,Int)]->[[Int]]
makeCycles [] _ = []
makeCycles x f = [cycle] ++ makeCycles (x \\ cycle) f
                 where cycle = getCycle f (head x)
                       
-- TODO: difference between type and newtype?
type F_permute = [(Int,Int)]

-- TODO: create a typeclass for a permutation function
--apply :: F_permute -> F_permute -> F_permute
--apply f g = map (\x -> getImage 


{-

testcase: create a test case by selecting the n-th permutation of list x
x: list from 1 to n.  [1..5]
n: n-th permutation, runs from 0 to n! - 1

Example
  testcase [1..5] 4

-}
testcase :: [a] -> Int -> [(a,a)]
testcase x n = zip x f
  where f = permutations x !! n

test m n = makeCycles l (testcase l n)
           where l = [1..m]
                 
exhaustive n = [test n x | x <- [0..(factorial n) - 1]]              
  where factorial n = product [1..n]


main = do
  mapM_ print (exhaustive 7)