Problem Link :- https://www.iarcs.org.in/inoi/2011/zio2011/zio2011-qpaper.pdf
Prerequisite :- Recursion, Permutation and Combinations
Reduced Problem Statement :-
For given N distinct numbers i.e 1…N there are in total N! possible permutations, out of
these permutations you have to find Kth smallest permutation.
Note - Permutation means each of several possible ways in which a set or number of things can be ordered or arranged.
Explanation :-
There are 2 major ways to solve this type of problem. They are :
- Apply brute force and find all possible permutations and then sort these permutations according to their numeric value and print the Kth smallest permutation.
- Apply some kind of Recursive algorithm that will help to find the number at a particular position such that all constraints are satisfied.
The first approach is not feasible for Pen and Paper-based exams because it will take a huge amount of time, for example, for N=6 there are 720 possible permutations, you will have to write all 720 permutations and then sort these permutations for finding Kth smallest permutation. ( However, this approach is feasible to solve using computer as constraints for this problem is 2<= N <= 9). So let us discuss the second approach in detail with this question in mind. Later you can apply this approach to solve other questions too.
Recursive Approach :-
This approach is kind of Mathematical type, so some basic facts that will be used to solve
this problem are :-
- The total number of permutations formed by N distinct integers is N!
- The total number of permutations formed by N distinct integers after fixing the first character is ( N-1 )!. Similarly, if we fix the first i characters, and there are (n-i) vacant positions, then the number of possible permutations is (n-i)!.
In this approach, we will find the character that will be present in our Kth smallest permutation at position i.
First, we have to understand that if we fix character at first i positions then there are (n-i)! Possible permutations. Hence for each character at the ith position, there are (n-i)! Permutations, for example, if N was 5 and we currently have 2 3_ _ _ ( where _ represents unknown characters ) then the remaining characters are 1,4,5 so we have 3! = 6 in total.
So using K we will find what character Kth permutation will have at the ith position.
Hence after fixing the ith character, there are ( n-i ) positions and hence (n-i)!
Hence if permutations are sorted then -
- The first smallest character will be in first ( n-i )! Permutations,
- The second smallest character will be in second (n-i)! Permutations, and so on…
In short, the jth character will be from ( j-1 )( ( n-i )! ) + 1 to ( j( n-i )! ) permutation, also we want Kth permutation ( we will maintain K i.e K<= ( n-i+1 )!, I will explain it in the next paragraph ), so character at ith position will be ceil ( K/( n-i )!).
( Note - the ceil function returns the smallest integer that is greater than or equal to x ie: rounds up the nearest integer. )
So now we have got our character for ith position now we know that for ( ( j-1 )( n-i )! + 1 ) to ( j(n-i)! ) smallest permutations j will be present at ith position, hence ( (j-1)(n-i)! + 1 ) <= K <= ( j( n-i ) ) and we cannot use j for further positions.
We will now find the character at ( i+1 ) position, but for that, we need to update K because we need to narrow down our range hence our new K will be K’ = K - ( ( j-1 )*( n-i )! ), and this step of finding character at ith position will be done recursively.
Let find( N, K, i, set of available character ) be a function that will find the character at the ith position, hence its definition will be:
find( N,K,i,set of available characters ){
if( i>N )
return;
J = ceil ( K/( N-i )! )
Print Jth smallest character from set of available character
Delete Jth smallest character from set
K = K - ( J-1 )*( N-i )!
find( N,K,i+1,set of available character )
}
Solving Sample test case :-
N = 3 , K = 4 , S = { 1,2,3 }
Call for find( 3,4,1,{ 1,2,3 } )
-
I = 1
J = ceil( K/( N-i )! ) = ceil( 4/( 3-1 )! ) = ceil( 4/(2)! ) = ceil( 4/2 ) = 2
Jth smallest character available from S is 2
Hence character at 1st position is 2
Update S to { 1,3 }
K = K - ( J-1 )( N-i )! = 4 - ( 2-1 )( 3-1 )! = 4 - 2 = 2
Call for find( 3,2,2,{ 1,3 } ) -
I = 2
J = ceil( 2/( 3-2 )! ) = ceil( 2/1 ) = 2
Jth smallest character available from S is 3
Hence character at 2nd position will be 3
Update S to { 1 }
K = K - ( J-1 )( N-i )! = 2 - (1)(3-2)! = 2-1 = 1
Call for find( 3,1,3,{ 1 } ) -
I = 3
J = ceil( 1/(3-3)! ) = ceil( 1/1 ) = 1
Jth smallest character available from S is 1
Hence character at 3rd position will be 1
K = K - ( J-1 )( N-i)! = 1 - (0)(0)! = 1
Call for( 3,1,4,{} )
Hence answer for N=3 and K = 4 will be 2 3 1
Solving Subtasks :-
1 ) N = 5, K = 76
Solution:
Answer = _ _ _ _ _
- N = 5, K = 76, I = 1, S = { 1,2,3,4,5 }
J = 4
Answer = 4 _ _ _ _
K = 76 - 72 = 4
S = { 1,2,3,5 }
I = I + 1 = 2 - N = 5, K = 4, I = 2 , S = { 1,2,3,5 }
J = 1
Answer = 4 1 _ _ _
K = 4 - 0 = 4
S = { 2,3,5 }
I = I + 1 = 3 - N = 5, K = 4, I = 3, S = { 2,3,5 }
J = 2
Answer = 4 1 3 _ _
K = 4 - 2 = 2
S = { 2,5 }
I = I + 1 = 4 - N = 5, K = 2, I = 4, S = { 2,5 }
J = 2
Answer = 4 1 3 5 _
K = 2 - 1 = 1
S = { 2 }
I = I + 1 = 5 - N = 5, K = 1, I = 5, S = { 2 }
J = 1
Answer = 4 1 3 5 2
K = 1 - 0 = 1
S = {}
I = I + 1 = 6
Hence answer is 4 1 3 5 2
2 ) N = 7 , K = 4197
Solution :
Answer: _ _ _ _ _ _ _
-
N = 7, K = 4197, I = 1, S = { 1,2,3,4,5,6,7 }
J = 6
Answer = 6 _ _ _ _ _ _
K = K - 5*720 = 597
S = { 1,2,3,4,5,7 }
I = I + 1 = 2 -
N = 7, K = 597, I =2, S = { 1,2,3,4,5,7 }
J = 5
Answer = 6 5 _ _ _ _ _
K = K - 4*120 = 117
S = { 1,2,3,4,7 }
I = I + 1 = 3 -
N = 7, K = 117, I = 3, S = { 1,2,3,4,7 }
J = 5
Answer = 6 5 7 _ _ _ _
K = K - 4*24 = 21
S = { 1,2,3,4 }
I = I + 1 = 4 -
N = 7, K = 21, I = 4, S = { 1,2,3,4 }
J = 4
Answer = 6 5 7 4 _ _ _
K = K-3*6 = 3
S = { 1,2,3 }
I = I + 1 = 5 -
N = 7, K = 3, I = 5 , S = { 1,2,3 }
J = 2
Answer = 6 5 7 4 2 _ _
K = K - 1*2 = 1
S = { 1,3 }
I = I + 1 = 6 -
N = 7,K = 1,I = 6,S = { 1,3 }
J = 1
Answer = 6 5 7 4 2 1 _
K = K - 0*1 = 1
S = { 3 }
I = I + 1 = 7 -
N = 7, K = 1,I = 7, S = { 3 }
J = 1
Answer = 6 5 7 4 2 1 3
K = K - 0*1 = 1
S = { }
I = I + 1 = 8
Hence Answer is 6 5 7 4 2 1 3
3 ) N = 9 , K = 191082
Answer = _ _ _ _ _ _ _ _ _
-
N = 9,K = 191082, I = 1, S = { 1,2,3,4,5,6,7,8,9 }
J = 5
Answer = 5 _ _ _ _ _ _ _ _
K = K - 4*40320 = 29802
S = { 1,2,3,4,6,7,8,9 }
I = I + 1 = 2 -
N = 9,K = 29802, I = 2, S = { 1,2,3,4,6,7,8,9 }
J = 6
Answer = 5 7 _ _ _ _ _ _ _
K = K - 5*5040 = 4602
S = { 1,2,3,4,6,8,9 }
I = I + 1 = 3 -
N = 9,K = 4602, I = 3, S = { 1,2,3,4,6,8,9 }
J = 7
Answer = 5 7 9 _ _ _ _ _ _
K = K - 6*720 = 282
S = { 1,2,3,4,6,8 }
I = I + 1 = 4 -
N = 9, K = 282, I = 4, S = { 1,2,3,4,6,8 }
J = 3
Answer = 5 7 9 3 _ _ _ _ _
K = K - 2*120 = 42
S = { 1,2,4,6,8 }
I = I + 1 = 5 -
N = 9, K = 42 , I = 5 , S = { 1,2,4,6,8 }
J = 2
Answer = 5 7 9 3 2 _ _ _ _
K = K - 1*24 = 18
S = { 1,4,6,8 }
I = I + 1 = 6 -
N = 9, K = 18, I = 6, S = { 1,4,6,8 }
J = 3
Answer = 5 7 9 3 2 6 _ _ _
K = K - 2*6 = 6
S = { 1,4,8 }
I = I + 1 = 7 -
N = 9, K = 6, I =7, S = { 1,4,8 }
J = 3
Answer = 5 7 9 3 2 6 8 _ _
K = K - 2*2 = 2
S = { 1,4 }
I = I + 1 = 8 -
N = 9,K = 2, I = 8, S = { 1,4 }
J = 2
Answer = 5 7 9 3 2 6 8 4 _
K = K - 1*1 = 1
S = { 1 }
I = I + 1 = 9 -
N = 9, K = 1, I = 9,S = { 1 }
J = 1
Answer = 5 7 9 3 2 6 8 4 1
K = K - 0*1 = 1
S = { }
I = I + 1 = 10
Hence Answer is 5 7 9 3 2 6 8 4 1
Bonus Question :-
In the above problem, you were given N distinct integers but what if you are given N
integers but they are not distinct for example N = 7, S = { 1,1,1,1,2,2,3 } and K = 1029