CODEWITHSUNDEEP
algorithmprologpermutation
A.A.
A.A.

Reputation: 1047

count number of permutations in a cycle

I have a permutation of numbers 1 to n. in each turn a permutation function is used to map the current permutation to a new one.

The function is defined by F(i) = p[i] which maps each element of the current permutation to a position in the new permutation. Since this function is injective and surjective, it can be proved that we always get to the first permutation again. (It's actually a cycle in the permutations graph)

for example [2,3,1] -> [3,1,2] -> [1,2,3] -> [2,3,1] so the cycle length is 3 since the first and last permutations are the same and we're stuck in a loop.

As input I have a special kind of permutation like this:

[2,1, 
4,5,3, 
7,8,9,10,6,
17,11,12,13,14,15,16,
18,19,20, 
29,21,22,23,24,25,26,27,28,
40,30,31,32,33,34,35,36,37,38,39,
53,41,42,43,44,45,46,47,48,49,50,51,52]

It's made of some sub-permutations (each line has a set of numbers which belong to the set of their indexes)

My question is what's the minimum number of moves needed to get to the first permutation again.

As a practice problem in prolog I want to calculate the number of moves for each sub-permutation and get their lcm but I'm not sure how to implement this (how to count the number of moves for each sub-permutation)

Any help would be appreciated

Upvotes: 1

Views: 539

Answers (1)

coproc
coproc

Reputation: 6257

A permutation p can be seen as a bijective function from the set {1,2,...,n} onto itself. Now what you seem to ask for is the minimal number of concatenations of this permutation with itself p o p o ... o p (where o is the concatenation operator with (f o g)(i) := f(g(i))) s.t. you get the identity permutation p0 with p0(i) = i.

You have a permutation that can be easily decomposed into cycles 1->2->1, 3->4->5->3, 6->7->8->9->10->6, ... Each cycle needs as many concatenations with itself as it has members to get the identity. Since you have cycles of lengths 2, 3, 5, 7, 3, 9, 11, 13 it takes 2*9*5*7*11*13 (the least common multiple) concatenations until all cycles are run through at the same time for the first time.

Upvotes: 1

Related Questions