C# - permutation counting solution


  • 0

    The idea is that you for n digits you can produce n! permutations. So, if you need the kth permutation you need to find the number of digits n which can produce more than k permutations and n -1 which can produce less than k permutations. You can jump ahead (n-1)! permutations by "incrementing" the nth digit. Take as many "increments" as you can until k is less than (n-1)! Here "increment by x" means take the next x highest available number and slide it to the front (by sliding it to the front you always keep the remaining numbers sorted). Then repeat with whatever remaining amount of permutations are left.

    public class Solution
    {
        public string GetPermutation(int n, int k)
        {
            int[] num = new int[n];
            for (int i = 0; i < n; i++) num[i] = i + 1;
    
            Permute(num, k - 1);
            return string.Join("", num);
        }
    
        public void Permute(int[] num, int k)
        {
            if (k <= 0) return;
            if (k == 1)
            {
                Move(num, num.Length - 2, num.Length - 1);
                return;
            }
    
            int pos = 1;
            while (Factorial(pos) <= k) pos++;
            int index = num.Length - pos;
            int delta = 0;
            int posFac = Factorial(pos - 1);
            while (k >= posFac)
            {
                delta++;
                k -= posFac;
            }
            Move(num, index, index + delta);
            Permute(num, k);
        }
    
        public void Move(int[] num, int left, int right)
        {
            int t = num[right];
            while (right > left)
            {
                num[right] = num[right - 1];
                right--;
            }
            num[left] = t;
        }
    
        public int Factorial(int x)
        {
            int f = 1;
            while (x > 0)
            {
                f *= x;
                x--;
            }
            return f;
        }
    }
    

Log in to reply
 

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