Nth K-Permutation

---

In combinatorics, generating N^th k-Permutation directly without explicitly computing/generating and listing down all the preceding k-permutations is important because the number of permutations is astronomical for sets of larger size. The total number of k-permutations for a set of size S is ^sP_k = S!/(S-k)!. For s=100 and k=50, ^sP_k = ¹⁰⁰P₅₀ = 3.068518756 x 10⁹³. For such a large number, generating all permutations might take months, which is not practical. The N^th k-permutation algorithm provides the means to generate directly the N^th permutation. There can be two ways we can define the Nth k-permutation:

1. In lexicographical order of permutations and
2. In combination order. That is, in lexicographical order of combinations in the permutation sequence, i.e., first generating all the permutations for a first combination before generating permutations of the next possible combination.

Generating N^th k-Permutation in lexicographic order

This can be achieved by using a Permutational number system, which is a generalised form of the Factorial number system, and is introduced in JNumberTools, an open source combinatorics library by Deepesh Patel. It is also known as Permutadic for short.

Description

To generate the N^th k-permutation of a set of size S, using permutadic, first convert the number to its equivalent permutadic string and then find the correct mapping between the permutadic digits and the list of numbers from 0 to S. The mapping process starts by using the leftmost permutadic digit and then removing the numbers from a list at a given index.

Example

Suppose we need to find the 5050^th 5-permutation of 8 digits. First we convert 5050 to permutadic, which will result in a sequence [6, 0, 0, 2, 2], so from our set of 8 digits [0, 1, 2, 3, 4, 5, 6, 7] we first remove the value at the 6^th index, which is 6. After this, the remaining permutadic digits will be [6, 0, 0, 2, 2] and the list will be [0, 1, 2, 3, 4, 5, 7]. Continue this process and the sequence of digits obtained will be the 5050^th permutation (starting from 0). The complete calculation is illustrated in the table below.

Permutadic	List containing remaining numbers	index	value removed at index	Sequence Formed
[6, 0, 0, 2, 2]	[0, 1, 2, 3, 4, 5, 6, 7]	6	6	[6]
[6, 0, 0, 2, 2]	[0, 1, 2, 3, 4, 5, 7]	0	0	[6, 0]
[6, 0, 0, 2, 2]	[1, 2, 3, 4, 5, 7]	0	1	[6, 0, 1]
[6, 0, 0, 2, 2]	[2, 3, 4, 5, 7]	2	3	[6, 0, 1, 3]
[6, 0, 0, 2, 2]	[2, 4, 5, 7]	2	5	[6, 0, 1, 3, 5]

Algorithm

In actual implementation, finding the permutadic and mapping it to the corresponding Nth k-permutation, both these steps can be combined for optimisation, and the below mentioned algorithm is doing the same.

Given:

• s = total number of items.
• n = positive integer to jump to
• k = size of permutation (0<=k<=S)
• L = list of numbers containing numbers 0, 1, 2.. k-1
• O=initially empty output list

Algorithm Steps:

1. compute max_allowed = ^sP_k
2. If n > ^sP_k return. //k-permutation does not contain the n^th digit. out of reach
3. compute divisor = ^s-1P_k-1
4. compute next = n-1
5. for i = 1 to k
   1. C_k-i = N/divisor //calculating permutadic digit
   2. N = N mod divisor
   3. divisor = divisor / next
   4. next = next -1
   5. O[i-1] = L[C_k-i] //finding corresponding mapping in the same loop
6. return O

Generating N^th k-Permutation in combination order

Background

Knowledge of the following topics is necessary to understand the below mentioned algorithm:

• Factorial number system:

• Combinatorial number system:

• k-permutation generation: k-permutation is a set of all unique permutations of size k where 0<=k<=S, where S is the number of items. Finding k-permutations is a 2-step algorithm-

1. Find all combinations of size k in lexicographical order (using the standard algorithm for unique combinations)
2. For all combinations in step 1, find all k! unique permutations in lexicographical order.

Algorithm description

Suppose we need to find the N^th k-permutation instead of the N^th unique permutation, in lexicographical order. The Factorial-Number-System clearly will not be able to generate the correct values for N > ^sC_k as after ^sC_k permutations, the sequence will change and start with the next unique combination). The solution lies in the algorithm to generate k-permutations in lexicographical order. In step 2 of k-permutation we generate unique permutations, and hence the Factorial-Number-System will work correctly to find the N^th value if N < k!. Now suppose our value is slightly greater than k! but less than 2*k! (N> k! and N < 2*k!).

What can we do in this case? We already know the number of permutations in step 2 is k!, so clearly we can jump to the next combination, say C₁ (assuming 0-based index) via combinadic and then use the factorial-number-system starting from C₁ to find the (N-k!)^th value using the factorial-number-system. That is, taking C₁ as the 0^th permutation and finding the (N-k!)^th permutation, which is the desired permutation. Now take another example where N > J * k! and N< ^sP_k where J is any positive integer. Now we know that -

• The size of sequential permutations in step 2 above, for each combination from step 1 is k!

• We can jump to any combination, say the M^th combination via the Combinatorial-Number-System in lexicographical order because we also know the number of combinations is ^sC_k.
• From the above information, we can first find J = N/k!. This will give us the correct combination number to jump to, which we can then reach via the Combinatorial-Number-System. Then we will find the correct value of the permutation via modulo division and then jump to the desired permutation number, taking the latest combination as the starting point via the Factorial-Number-System and corresponding Lehmer-code.

Algorithm

Given:

• S = Total number of items.
• N = positive integer to jump to
• K = size of permutation (0<=k<=S)

Algorithm Steps:

1. Let I = N (positive integer to jump to)
2. Let J = no. of permutations for a given C = ^sP_k/ ^sC_k = k!
3. For I = N, step N, till I < ^sP_k repeat step 4-7
4. Let C-skip = I/J
5. Let P-skip = I mod J
6. Use the Combinatorial-Number-System to generate the C-skip^th combination starting from the 0^th permutation. You can also use Gosper's hack instead of the standard algorithm if the number of bits in the 'int' variable is sufficient (>=S)
7. N^th k-permutation = Find the P-skip^th permutation by using factoradic and the corresponding Lehmer code (taking the C-skip^th combination from step 6 as the 0^th permutation).

References

This article "Nth K-Permutation" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Nth K-Permutation. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Ideal ring bundle
• Lattice ball
• Aharoni-Korman conjecture
• Combinatorial hierarchy

---