An iterative solution for reference


  • 60
    A

    Recursion will use more memory, while this problem can be solved by iteration. I solved this problem before, but I didn't realize that using k = k-1 would avoid dealing with case k%(n-1)!==0. Rewrote this code, should be pretty concise now.

    Only thing is that I have to use a list to store the remaining numbers, neither linkedlist nor arraylist are very efficient, anyone has a better idea?

    The logic is as follows: for n numbers the permutations can be divided to (n-1)! groups, for n-1 numbers can be divided to (n-2)! groups, and so on. Thus k/(n-1)! indicates the index of current number, and k%(n-1)! denotes remaining index for the remaining n-1 numbers.
    We keep doing this until n reaches 0, then we get n numbers permutations that is kth.

    public String getPermutation(int n, int k) {
            List<Integer> num = new LinkedList<Integer>();
            for (int i = 1; i <= n; i++) num.add(i);
            int[] fact = new int[n];  // factorial
            fact[0] = 1;
            for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
            k = k-1;
            StringBuilder sb = new StringBuilder();
            for (int i = n; i > 0; i--){
                int ind = k/fact[i-1];
                k = k%fact[i-1];
                sb.append(num.get(ind));
                num.remove(ind);
            }
            return sb.toString();
        }

  • 36
    M

    Thanks for your post and explanation.

    I think linkedlist is as efficient as you can get in order to store the remaining numbers. Linkedlist may require counting index to get to the number, but it is more efficient than an array for removing elements. I haven't seen a better solution yet.

    We can reduce the memory usage for factorial a little by using just one integer, since we are going down in factorial anyway.

    I think you meant "permutations can be divided into n groups with (n - 1)! elements in each group". Thus, k / (n - 1)! is the index among current n groups, and k % (n - 1)! is the index for next iteration.

    public String getPermutation(int n, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) list.add(i);
        int fact = 1;
        for (int i = 2; i <= n; i++) fact *= i; // factorial
        
        StringBuilder strBuilder = new StringBuilder();
        for (k--; n > 0; n--) {
            fact /= n;
            strBuilder.append(list.remove(k / fact));
            k %= fact;
        }
        
        return strBuilder.toString();
    }

  • 0
    B
    class Solution:
    # @return a string
    def getPermutation(self, n, k):
        if n==1:
            return "1"
        factorial=[0]*(n+1)
        factorial[0]=1
        factorial[1]=1
    
        for i in range(2,n+1):
            factorial[i]=factorial[i-1]*i
    
    
        candidate=[str(x) for x in range(1,n+1)]
        result=[]
    
        position=n
        k=k-1
        while position>=1:
        # k is betwwen factorial[position] and factorial[position+1]
            multiple=k//factorial[position-1]
            remaining=k%factorial[position-1]
            result.append(candidate.pop(multiple))
            if remaining==0:
                result.extend(candidate)
                break
            k=remaining
            position-=1
    
        return "".join(result)
    

    The same idea..
    in python


  • 0
    S

    great answers! thanks a lot


  • 0
    H

    More edition to your description of this idea:

    For n numbers, permutations can be divided into n groups with (n - 1)! elements in each group. Thus, k / (n - 1)! is the group index among the current n (to be) sorted groups, and k % (n - 1)! is the sequence number k for next iteration.


  • 0

    I have a solution with similar idea but I didn't use additional space to store the remaining elements.

    Here is the main idea:

    First, I create the array, let's say [1,2,3,4].

    Second, based on the k, I will pick a certain element to place in the 0th position. Let's say we pick element 3 and the remaining array is [1,2,4]. Instead of storing the remaining elements in a separate lists, what I did is move 3 to the 0th position and shift [1,2] towards right by 1 position. Then the list become [3,1,2,4] and we know the remaining list by reading the array from the 1st position

    public class Solution {
    
        // k is 1-based
        public String getPermutation(int n, int k) {
            int[] nums = getNums(n);
            permute(nums, k-1);
            return convertArrayToString(nums);
        }
       
        // k is 0-based
        public void permute(int[] nums, int k) {
            int divisor = fact(nums.length-1);
            for ( int i = 0; i <= nums.length-2; i++ ) {
                int swapTime = k/divisor;
                for ( int j = 1; j <= swapTime; j++ ) { swap(nums, i, i+j); }
                k %= divisor; divisor /= nums.length-i-1;
            }
        }
        
        // Helper Method
        public int fact(int n) { return n <= 1 ? 1 : n*fact(n-1); }
        public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
        public String convertArrayToString(int[] arr){
            StringBuffer s = new StringBuffer();
            for ( int element : arr ) { s.append(element); }
            return s.toString();
        }
        public int[] getNums(int n) {
            int[] nums = new int[n];
            for ( int i = 0; i < nums.length; i++ ) { nums[i] = i+1; }
            return nums;
        }
    }
    

  • 0
    R

    complexity please


  • 1
    H

    Good solution. But I believe it is meaningless to discuss the operation on a list with at most of len 9


  • 0

    Best answer!


  • 0

    LinkedList may be efficient at removing things, but it's slow at locating things and remove(k / fact) needs to locate the element first, which is O(n). You can get instant removals when using iterator.remove(), but I can't figure out how to apply it to this problem. As it is, LinkedList solutions are bound to be slower than ArrayList because of its slower nature.


  • 0
    V

    What's the complexity for this problem? Is it O(N) , any idea?


  • 0
    Z

    I think it's O(1) since n cannot be larger than 9.


  • 0
    I

    TLE for input:
    8
    8590

    So leetcode added more test case?


  • 0

    k = k-1 is not intuitive, here is verbose code if not doing it, which is more intuitive.
    e.g. 1234 for k = 6, we should keep 1 and reverse 234, note that the last state of permutation is always the reverse of the sequence.

    public String getPermutation(int n, int k) {
        List<Integer> num = new LinkedList<Integer>();
        for (int i = 1; i <= n; i++) num.add(i);
        int[] fact = new int[n];  // factorial
        fact[0] = 1;
        for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; i--) {
            if(k%fact[i-1]==0) { // we already found it
                int ind = k/fact[i-1]-1;
                sb.append(num.get(ind));
                num.remove(ind);
                Collections.reverse(num); // the final state is the reverse of rest number
                for(int d : num)
                    sb.append(d);
                return sb.toString();
            } else {
                int ind = k/fact[i-1];
                k = k%fact[i-1];
                sb.append(num.get(ind));
                num.remove(ind);
            }
        }
        return sb.toString();
    }

  • 0
    B

    @pinkfloyda
    I am confused with the k=k-1, Could you please give me more explanation about why we need k=k-1?


  • 3

    example:
    n = 4, k = 14:

    1. We have {1, 2, 3, 4}, find the 14th permutation.

    List out all the permutations:

    1 + (permutations of 2, 3, 4)
    2 + (permutations of 1, 3, 4)
    3 + (permutations of 1, 2, 4)
    4 + (permutations of 1, 2, 3)

    To find the 14th, we can see it falling to range 3 + (permutations of 1, 2, 4), since 1 + (permutations of 2, 3, 4) and 2 + (permutations of 1, 3, 4) could take the first 12 permutations. So we can know the first number of result is 3.

    1. Then the question turn to be a smaller problem.
      {1, 2, 4}, find the 2nd permutation.

    List out all the permutations:
    1 + (permutations of 2, 4)
    2 + (permutations of 1, 4)
    4 + (permutations of 1, 2)

    There are 2 + 2 + 2, 6 permutation. The 2nd must be in range 1 + (permutations of 2, 4). So we can know the second number of result is 1.

    1. So the question turn be a smaller problem.
      {2, 4}, find the 2nd permutation. The answer is (4, 2).

    So the final result is (3, 1, 4, 2)

    public String getPermutation(int n, int k) {
        
        List<Integer> nums = new LinkedList();
        StringBuilder res = new StringBuilder();
    
        int[] f = new int[n];
        f[0] = 1;              // 0's factorial is 1
    
        for(int i = 1; i < n; i++){
          nums.add(i);
          f[i] = f[i - 1] * i;
        }
        nums.add(n);
    
        k--;   // 14th count from 1, turn to be 13th count from 0.
    
    
        for(int i = n; i > 0; i--){
          int idx = k / f[i - 1];
          k = k % f[i - 1];
    
          res.append(nums.get(idx));
          nums.remove(idx);
        }
        return res.toString();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.