Solving Permutations Problems: Finding Algorithms & Optimizing Efficiency

[alejandrito]

I have two problems on permutations which I can´t solve now becuase my knowledge about permutations and the necessary tricks is very poor.
1st:
Find an algorithm that for given natural N (N<=1000), K and given permutation of N elements will find the Kth composition of this permutation in time less or equal to O(N log K).
2nd:
Find an algorithm that fot given natural N (N<=1000) and given permutation of N elements will determine the number of all cycles that the permutation is composed from in time less or equal to O(n).
Can anybody give me some hint related with any of this two problems, I´m mainly confused as to the satisfaction the maximal possible effecienty.

 

[dduardo]

This sounds like a homework problem. Can you show use any type of thought process before we start giving you hints.

 

[-Job-]

Here's an example of a Permutation P on n=4 elements:

|x1 x2 x3 x4|
| 4  3  2  1|

This Permutation P sends element x1 to #4 spot, x2 to #3 ...etc, producing:

|x4 x3 x2 x1|

What happens if you apply permutation P twice? Then:

|x1 x2 x3 x4|
| 4  3  2  1|
|x4 x3 x2 x1|
| 4  3  2  1|
|x1 x2 x3 x4|

This would be the second composition of P. Notice that the resulting permutation of the 2nd Composition of P is the original arrangement of the n elements, so this is a cycle. Of course this isn't the case for every possible P. Suppose that a permutation Q moves each element xi one place to the right (wrapping around), then, it will go back to the original arrangement only at the nth (in this case the 4th) composition of Q.
In your first question you're asked to find the kth composition of a permutation P. Obviously you can do this in O(Nk) time (n elements and k applications of permutation P). You need to squeeze this into O(N log k). Here's a strategy:
Let A1 be a permutation equal to two applications of permutation P. Then let A2 be a permutation equal to two applications of permutation A1 (4 of P). Let A3 be two applications of A2 (8 of P).. etc. Then, if k = 8:
the permutation A3 gives you the kth composition of P. If k = 9, then A3 followed by P gives you the kth composition of P. If k = 10, then A3 followed by A1 gives you the kth composition of p ..etc. If k > 16 then you need to compute A4, and so on. This takes at most 2*N*log k = O(N log k).
Now all you need is to do is turn this into an algorithm which should be easy enough.