Questions about Variants for 5-10 and 5-11 (new edition)

#1

Hi All,

Question 1:

The variant for question 5-10 go like this: Given an array A of integers representing a permutation, update A to represent the inverse permutation using only constant additional storage.

What does inverse mean in that context? Let’s say A is {2, 0, 1, 3} which represent a permutation Array. Would the inverse permutation be {3, 1, 0, 2}? I don’t understand the question. What’s an example of an inverse permutation?

Question 2:

The variant for Question 5-11 ask to compute the kth permutation under dictionary ordering starting from the identity permutation.

All I can think is use the algorithm given in the book and loop k time. Therefore the time complexity would be O(kn). It will be O(n^2) at worst.

Is it possible to design a tighter algorithm that can directly gets you to the kth permutation enumeration all the k - 1 permutation that’s not even needed before reaching to the kth one? I mean a O(n) algorithm.

Thanks!
JC

0 Likes
#2

+1 not able to understand what inverse means in the above context.

0 Likes
#3

Hi @joc,

For Question 1:
The definition of inverse permutation http://mathworld.wolfram.com/InversePermutation.html.

For Question 2:
Yes, it is possible to do something better than O(kn) but it requires understanding how many permutations after a certain number at certain index. For example, assuming there are only 4 numbers (i.e., 1, 2, 3, 4). If you see a permutation of 4xxx, then you know this permutation must appear after at least 3 * 3! = 18 since all 1xxx, 2xxx, 3xxx appear before 4xxx. With this, you shall be able to calculate the ordering of kth dictionary order of a permutaiton.

0 Likes