In this article, we will understand and explore about the concept of generating k-th lexicographical permutation of first N integers. There are O(N!) permutations but you can find it in O(N) time.

Table of contents

• Permutation sequence
• k^th permutation of first n integers
• Complexity analysis

This is similar to Leetcode problem 60. Permutation Sequence. Let us get started with this problem.

Permutation Sequence

Literally, permutation is the arrangement of objects in a definite order. Mathematically, permutation determines the number of ways in which the elements of a set can be arranged, where the order of arrangement matters the most. The mathematical formula to determine the permutation is given by:

ⁿP_r = n!/(n-r)!

where,

• ⁿP_r = total number of permutations
• n = total number of objects
• r = number of objects selected.

A permutation sequence is a n length array that contains all the possible permutations of the given set.

As far as coding is concerned, when we encounter a problem to generate permutation sequence, we consider r in the above given formula to be n everytime as we generate the permutation sequence for all the numbers in the given set and do not choose certain elements from the set to generate the permutation sequence. Hence we will have n! unique permutations for any given value of n.

k^th permutation of first n integers

In this problem, we would be given two numbers k and n and will be required to find the k^th permutation of the numbers from 1 to n.

For example, let n=3 and k=4 i.e we need to find the 4^th permutation in the permutation sequence of (1, 2, 3).

There are two ways to tackle this problem.

One is to generate the permutation sequence for the set containing numbers from 1 to n, arrange them in the order that we want and then pick out the integer in the k^th position directly for our answer. But this is a time consuming process. We need to generate the whole sequence to just find one number. Hence this method is not preferred and we opt for the second way to find the k^th permutation.

The second method is to find a pattern in the permutation sequence that will eventually help us in finding the k^th permutation without having to find all possible permutations. The algorithm to this method is discussed below.

Algorithm

• Initialize the string result to store the answer.
• Initialze a list which contains values from 1 to n.
• While n>0:
  * Find the number of permutations which is equal to (n-1)!
  * Find the index at which the k exists as k/(n-1)!
  * If k % (n-1)! =0, then index=index-1
  * Add the value at index position in the list into result and remove the value from the list.
  * Decrement n by 1
• Return the result.

Working of the algorithm

Let us understand how this algorithm works with the help of an example.
Let n=4 and k=9 i.e we need to find the 9^th permutation in the permutation sequence of set (1, 2, 3, 4).

• Initialization:
  
• Iteration 1:
  
• Iteration 2:
  
• Iteration 3:
  
• Iteration 4:
  

Since, n=0 after iteration 4, the program comes out of the while loop and the result is printed. Therefore, the 9^th permutation of set (1, 2, 3, 4) is 2314 as per the algorithm described.

Python implementation

To implement the algorithm, we define two functions: findNumIndex() and findKthPermutation().

Function to find the index of the element

def findNumIndex(k, n):
	if (n == 1):
		return 0, k	
	n -= 1    #so that we find factorial of (n-1)
	num_index = 0
	n_fact = n
    #Calculating factorial of (n-1)
	while (k >= n_fact and n > 1):  
		n_fact = n_fact * (n - 1)
		n -= 1
    #Calculating the index
	num_index = k // n_fact
    #Updating k value
	k = k % n_partial_fact

	return num_index, k

We first define a function findNumIndex() that takes k and n as inputs. The factorial of (n-1) is then found by using a while loop with the condition n >1 and k is greater than or equal to the factorial. After each iteration of while loop, the value of n is decremented by 1. The function then calculates the index of the number, updates the value of k and returns both the index of the number and the k value.

Function to find the k^th Permutation

def findKthPermutation(n, k):

	# To store final answer
	result = ""

	s = set()

	# Insert all natural number upto n in set
	for i in range(1, n + 1):
		s.add(i)

	# Subtracting 1 to get 0 based indexing
	k = k - 1

	for i in range(n):

		
		array = list(s)

		index, k = findNumIndex(k, n - i)

	# array now points to the number at index in set s
		result += str(array[index])

		# remove current number from the set
		array.pop(index)
		
		s = set(array)
	
	return result

We then define a function findKthPermutation() that also takes n and k as inputs. An empty string result is created to store the final answer and an empty set s. Using for loop, all the numbers from 1 to n are inserted into the set. The k value is decremented by 1 to support the 0-based indexing followed in python.

Using for loop, we iterate over all the elements in set s and for each iteration, the following actions are executed:

• Convert the set s into a list and store it in a variable array.
• The index and k-value are found by calling the findNumIndex() function.
• The element in that index position in array is coverted to string and added into result.
• That particular element is deleted from array.
• array is converted back to a set.

The function then returns the result after it comes out of the for loop.

Driver code

if __name__=='__main__':

	n = 4
	k = 9
	
	kth_perm_seq = findKthPermutation(n, k)

	print(kth_perm_seq)

Here, we initialize the required n and k value and call the findKthPermutation() function to obtain the result.

Output

2314

Complexity analysis

The algorithm discussed above in this article at OpenGenus has a time complexity of O(N) and space complexity of O(N) where N is the number of elements in the list array in the python implementation.