New approach: directly find the kth permutation (k = 1...n!) with a simple loop


  • 8
    T

    Explanation

    The general idea is the following (same as other solutions):

    1. We know there are n! possible permutations for n elements.
    2. Enumerate them one by one

    Most solutions use the previous permutation to generate the next permutation or build it recursively.
    I had the idea to calculate the kth permutation directly from the input. Steps are as follows:

    1. Build a list of all elements in ascending order.
      The length of this list is n (i.e. not the original input size).
    2. Given k we know what the first element will be in the kth permutation of the current list.
      There are n groups in the lexicographical order of all permutations of the list. Inside a group each permutation's first element is the same. Each group has (n-1)! elements, so an easy k / (n-1)! will give us the index.
    3. Append the selected element to the result, i.e. the next element in the kth permutation.
    4. Remove the selected element from the list.
    5. Now the list has one less elements and we can repeat from Step 2 with k' = k % n!,
      that is the k'th permutation of the reduced list.

    Notice that it doesn't matter what the elements are because the indices are calculated.

    Examples for n = 1...4

    elements  k    indices
    []        -    -       =----- trivial
    
    [1]       0    0       =----- reduces to [] after selecting 1
    
    [1,2]     0    0 0     =----- reduces to [2] after selecting 1
    [2,1]     1    1 0     =----- reduces to [1] after selecting 2
    
    [1,2,3]   0    0 0 0   =\____ reduces to [2,3] after selecting 1
    [1,3,2]   1    0 1 0   =/
    [2,1,3]   2    1 0 0   =\____ reduces to [1,3] after selecting 2
    [2,3,1]   3    1 1 0   =/
    [3,1,2]   4    2 0 0   =\____ reduces to [1,2] after selecting 3
    [3,2,1]   5    2 1 0   =/
    
    [1,2,3,4] 0    0 0 0 0 =\
    [1,2,4,3] 1    0 0 1 0   \
    [1,3,2,4] 2    0 1 0 0    \__ reduces to [2,3,4] after selecting 1
    [1,3,4,2] 3    0 1 1 0    /
    [1,4,2,3] 4    0 2 0 0   /
    [1,4,3,2] 5    0 2 1 0 =/
    [2,1,3,4] 6    1 0 0 0 =\
    [2,1,4,3] 7    1 0 1 0   \
    [2,3,1,4] 8    1 1 0 0    \__ reduces to [1,3,4] after selecting 2
    [2,3,4,1] 9    1 1 1 0    /
    [2,4,1,3] 10   1 2 0 0   /
    [2,4,3,1] 11   1 1 1 0 =/
    [3,1,2,4] 12   2 0 0 0 =\
    [3,1,4,2] 13   2 0 1 0   \
    [3,2,1,4] 14   2 1 0 0    \__ reduces to [1,2,4] after selecting 3
    [3,2,4,1] 15   2 1 1 0    /
    [3,4,1,2] 16   2 2 0 0   /
    [3,4,2,1] 17   2 2 1 0 =/
    [4,1,2,3] 18   3 0 0 0 =\
    [4,1,3,2] 19   3 0 1 0   \
    [4,2,1,3] 20   3 1 0 0    \__ reduces to [1,2,3] after selecting 4
    [4,2,3,1] 21   3 1 1 0    /
    [4,3,1,2] 22   3 2 0 0   /
    [4,3,2,1] 23   3 2 1 0 =/
    

    Code

    The fact of FACT: since the problem asks for all permutations we can be sure it won't ask for more than 12 elements, because 13! is out of range for int and all lists are indexed by ints. Also 12! permutations of 12 elements in List<List> is good 7GiB worth of memory.

    public class Solution {
        private static final int[] FACT = { // 479001600 < 2147483647 < 6227020800
            1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
        };
        public List<List<Integer>> permute(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>(nums.length);
            for (int k = 0; k < FACT[nums.length]; ++k) {
                result.add(permutation(nums, k));
            }
            return result;
        }
        List<Integer> permutation(int[] nums, int k) {
            // k %= FACT[nums.length]; // in case you want to use it elsewhere
            List<Integer> source = toList(nums);
            List<Integer> result = new ArrayList(nums.length);
            while (!source.isEmpty()) {
                int f = FACT[source.size() - 1];
                result.add(source.remove(k / f));
                k %= f;
            }
            return result;
        }
        List<Integer> toList(int[] nums) {
            List<Integer> result = new LinkedList<>();
            for (int num : nums) {
                result.add(num);
            }
            return result;
        }
    }
    

    Analysis

    It's clear that we need to iterate n! times, because we're generating n! elements.
    The permutation method looks like O(n), but sadly it's O(n^2) because remove takes O(n):

    • LinkedList
      i steps to find the ith element and O(1) to remove it
    • ArrayList
      O(1) to find the ith element and n-i steps to remove the ith element
    • keep int[] nums and boolean[] removed
      we have to iterate over each removed item, so O(n)
    • Map<Integer, Integer>
      may be better, but we have to re-index all remaining elements
    • Is there a better data structure for this?

    Code variations

    In case you don't like the hardcoded FACT:

    /* 12! = 479001600 < Integer.MAX_VALUE = 2147483647 < 13! = 6227020800 */
    private static final int[] FACT = factorials(12);
    static int[] factorials(int n) {
        int[] f = new int[n+1];
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            f[i] = f[i-1] * i;
        }
        return f;
    }
    

    or it's even possible to calculate n! only once and keep reducing it, but then we have to pass an extra unrelated argument.

    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>(nums.length);
        int fact = factorial(nums.length);
        for (int k = 0; k < fact; ++k) {
            result.add(permutation(nums, fact, k));
        }
        return result;
    }
    List<Integer> permutation(int[] nums, int f, int k) {
        if (nums.length == 0) return Collections.emptyList();
        List<Integer> source = toList(nums);
        List<Integer> result = new ArrayList(nums.length);
        do {
            k %= f;
            f /= source.size();
            result.add(source.remove(k / f));
        } while (!source.isEmpty());
        return result;
    }
    static int factorial(int n) {
        if (n <= 1) return 1;
        int result = n;
        while (--n > 1) {
            result *= n;
        }
        return result;
    }

  • 2

    Yes, you can easily make permutation O(n):

    List<Integer> permutation(int[] nums, int k) {
        int[] source = nums.clone();
        int len = nums.length;
        List<Integer> result = new ArrayList(len);
        while (len-- > 0) {
            int f = FACT[len];
            result.add(source[k / f]);
            source[k / f] = source[len];
            k %= f;
        }
        return result;
    }
    

  • 0
    T

    Didn't run it, but that seems to shuffle the result...

    What if k/f gives index 0 twice in a row and source contains [1,2,3,4,5]? First index 0 points to 1, then source becomes [5,2,3,4,5] (last 5 ignored by len--) and second index 0 points to 5 instead of 2.


  • 0

    Yes, it enumerates differently, but since we're not asked for a specific order, that's fine.


  • 0
    T

    Ah, I carried over the lexicographical order from "Next Permutation" which I did just before this. Nice, thanks for the tip!


  • 0
    A

    In the line "Now the list has one less elements and we can repeat from Step 2 with k' = k % n!..."

    k' = k % n! should be K' = k%(n-1)!


  • 0
    T

    Yeah, I thought it might be confusing, it's hard to express timeliness in plain text algorithms. Notice that the sentence you quoted contains "now the list has one less elements" and above at point 1.:

    The length of this list is n (i.e. not the original input size).

    ... so n is already n-1. Let me know if you know how to make it more clear.


Log in to reply
 

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