Title:

Permutation Sequence

Specification:

The set [1,2,3,...,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note:
Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Examples:

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Initial Code and Signature:

``` public interface PermutationFinder { public String getPermutation(int n, int k); } ```

Algorithm:

Main Idea:
floor (k / (n-1)!) + 1 identifies the first number in the kth permutation sequence.
floor ( ( k % (n-1) ! + 1 ) / (n-2)!) + 1 identifies the second number in the kth sequence.
floor (((k % (n-1) ! + 1 ) / (n-2)! +1) / (n-3) !) + 1 identifies the third number in the kth sequence.
and so on....

1. Consider a list of integers containing numbers 1, ..., n.
2. Calculate floor (k / (n-1)!)
3. Calculate k % (n-1)!
4. If k > 0
1. Add number located at the position of floor (k / (n-1)!) to the kth permutation sequence.
2. Remove the added element from the list of numbers.
3. n = n-1
4. k = k % (n-1)!
5. go to (2-)
5. else (i.e; k = 0)
1. Add element number floor (k / (n-1)!) - 1
6. Add whatever element that has not been added in reverse order.

Run-Time Analysis:

GitHub Project:

Code:

``` /** * @author Mahsa Sadi * * @since 2020 - 04 - 09 * * License: Creative Commons * * Copyright by Mahsa Sadi * * * */ import java.util.*; public class PermutationFinderV2 implements PermutationFinder { /** * Problem: Permutation Sequence * * @see: https://leetcode.com/problems/permutation-sequence/ * * Description: * * The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" * * Given n and k, return the kth permutation sequence. * * Note: * Given n will be between 1 and 9 inclusive. * Given k will be between 1 and n! inclusive. * * * * Solution: * * Main Idea: * floor (k / (n-1)!) + 1 identifies the first number in the kth permutation sequence. * floor ( ( k % (n-1) ! + 1 ) / (n-2)!) identifies the second number in the kth sequence. * floor ( (k % (n-1) ! + 1 / (n-2)! + 1 ) / (n-3) !) identifies the third number in the kth sequence. * and so on..... * * * * * 1- Consider a list of integers containing numbers 1, ..., n. * * 2- Calculate floor (k / (n-1)!) * * 3- Calculate k % (n-1)! * * 4- If k > 0 * * add element number floor (k / (n-1)!) * remove the added element from the list of numbers * n = n-1 * k = k % (n-1) ! * go to (2-) * * 5- else (i.e; k = 0) * add element number floor (k / (n-1)!) - 1 * * 6- add whatever element that has not been added in reverse order. * * * * */ @Override public String getPermutation(int n, int k) { String KthPermutation = ""; List letters = new ArrayList (); int iMinusOneFactorial = getFactorial (n); for (int i = 1; i <= n; i++) letters.add(String.valueOf(i)); for (int i = n-1; i > 0; i--) { iMinusOneFactorial = iMinusOneFactorial / (i+1); if ( k >= iMinusOneFactorial) { int number = Math.floorDiv(k , iMinusOneFactorial); k = k % iMinusOneFactorial; if( k > 0) KthPermutation += letters.remove(number); else { KthPermutation += letters.remove(number - 1); break; } } else { KthPermutation += letters.remove(0); } } for(int i = letters.size() - 1; i >= 0; i-- ) KthPermutation += letters.remove(i); return KthPermutation; } public int getFactorial (int n) { int result = 1; for (int i = n; i > 0; i--) result *= i; return result; } } ```