CODEWITHSUNDEEP
listmathhaskellpermutation
user1173656
user1173656

Reputation: 103

Haskell: order of permutation

i'm new in Haskell. I have to write function that takes list of Integers and returns number of composition needed to recieve identity permutation. Something like that:

permutationOrder :: [Int] -> Int

I'd be grateful for any help.

Upvotes: 1

Views: 548

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183878

Assuming the list contains the numbers from 0 to n-1 in some order,

toPermutationGraph :: [Int] -> [(Int,Int)]
toPermutationGraph = zip [0 .. ]

gives you the graph of the permutation. From the graph, you can easily compute the order by partitioning it into connected components (corresponding to the cycles the permutation is composed of). The order of a cycle is the number of elements in the cycle. Disjoint cycles commute, that makes it easy to compute the order of a product of disjoint cycles.

Upvotes: 2

Related Questions