60.Permutation Sequence

Tags: [permutation], [math], [factorial], [trick]

Com: {t}

Hard: [####]

Link: 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 (ie, for n= 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution: Math

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        if n <= 0 or k <= 0:
            return ''

        factorial = 1
        nums = [0 for _ in xrange(n)]
        for i in xrange(n):
            elem = i + 1;
            factorial *= elem
            nums[i] = elem

        k -= 1 # adjust the k from 1-base to 0-base, making it easier to do mod later.
        ret = []

        while n > 0:
            factorial /= n # calculate the (n - 1)!, because n! / n = (n - 1)!
            index = k / factorial

            ret.append(nums[index])
            nums = nums[:index] + nums[index + 1:] # T = O(1), because n in the range[1, 9], there are at most 9 numbers.

            k %= factorial
            n -= 1

        return ''.join([str(x) for x in ret])

Revelation:

• 假设 n = 4, 那么一共就有 n! = 4! get permutation，我们如果把这些permutation都列出来的话，就想下面这样：

以 1 开头的： 1, permutation([2, 3, 4]), 因为 [2, 3, 4] 的个数是 n - 1, 所以 [2, 3, 4]有 (n - 1)! 个permutation
以 2 开头的： 2, permutation([1, 3, 4]), 因为 [1, 3, 4] 的个数是 n - 1, 所以 [1, 3, 4]有 (n - 1)! 个permutation
以 3 开头的： 3, permutation([1, 2, 4]), 因为 [1, 2, 4] 的个数是 n - 1, 所以 [1, 2, 4]有 (n - 1)! 个permutation
以 4 开头的： 4, permutation([1, 2, 3]), 因为 [1, 2, 3] 的个数是 n - 1, 所以 [1, 2, 3]有 (n - 1)! 个permutation

那么也就是说：
以 1 开头的permutation 有 (n - 1)! 个
以 2 开头的permutation 有 (n - 1)! 个
以 3 开头的permutation 有 (n - 1)! 个
以 4 开头的permutation 有 (n - 1)! 个

那么也就把所有的permutation分成了几个组.

如果我们把这些permutation label起来的话，就会是像下面这样：
label                          |   permutation
1                              |   1, ...
2                              |   1, ...
3                              |   1, ...
... ...                        |    ... ...
(n - 1)! + 1                   |   2, ...
(n - 1)! + 2                   |   2, ...
... ...                        |   ... ...
(n - 1)! + (n - 1)! + 1        |   3, ...
(n - 1)! + (n - 1)! + 2        |   3, ...
... ...                        |   ... ...

那么我们可以看出，如果我们想知道第 k 个 permutation 是以那个数字开头的，我们只要知道这个第k个permutation是在哪个‘group’里面的，

那么怎么知道k是在那个’group‘ 里的呢？
我们知道这些permutation分成了几个group，每个group有 (n - 1)! 个 permutation，
那么 k / (n - 1)! 就可以计算出当前k是落在第几个group中了,
我们可以依据n先把factorial计算出来，那么 (n - 1)! 就等于 factorial / n,
我们把数字1 - 9先放入nums中，

这样：
我们先 k = k - 1, 把k从1-base 变成 0-base
factorial = factorial / n
index = k / factorial # 算出这第k个permutation是在哪个组中
nums[index] # 找到这个组的开头数字
我们就能拿到当前第k个permutation的开头数字是nums[index]了，

然后因为这个数字已经被我们用了，我们要把这个数字从nums中移掉(想象一下，就想我们用recursion，这层已经处理完了，我们准备进入下一层了，这层用了的数字下一层就不能用了)，
然后再更新k = k % factorial (类似进入下一层'recursion'), 去算下一个数字该是什么.

Note:

• Time complexity = O(n), nums[:index] + nums[index + 1:] T = O(1), because there are at most 9 numbers in the array.

Java Solution: Math

public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }

        int factorial = 1;
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < n; i ++) {
            int elem = i + 1;
            factorial *= elem;
            nums.add(elem);
        }

        k --;

        List<Integer> ret = new ArrayList<>();
        while (n > 0) {
            factorial /= n;
            int index = k / factorial;
            ret.add(nums.get(index));

            nums.remove(index);

            k %= factorial;
            n --;
        }

        StringBuilder sb = new StringBuilder();
        for (Integer elem : ret) {
            sb.append(elem);
        }

        return sb.toString();
    }
}

Solution: Next Permutation

public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }

        int[] nums = new int[n];
        for (int i = 0; i < n; i ++) {
            nums[i] = i + 1;
        }

        // Calculate k - 1 times.
        for (int i = 0; i < k - 1; i ++) {
            nextPermutation(nums);
        }

        StringBuilder sbuilder = new StringBuilder();
        for (int elem : nums) {
            sbuilder.append(elem);
        }
        return sbuilder.toString();
    }

    private void nextPermutation(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        int size = nums.length;

        int left = size - 2;
        while (left >= 0 && nums[left] >= nums[left + 1]) {
            left --;
        }

        if (left < 0) {
            reverse(nums, 0, size - 1);
            return;
        }

        int right = size - 1;
        while (left < right && nums[left] >= nums[right]) {
            right --;
        }

        swap(nums, left, right);
        reverse(nums, left + 1, size - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start ++;
            end --;
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}

Note:

• Time complexity = O(k * n).