Given n and k, return the kth permutation sequence

Question

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.

For example, given n = 3, k = 4, ans = "231".

There are multiple solutions out there. But all of them uses either factorial or there complexity is larger than O(n) such as O(n!). If you use factorial and find the number at the position by k/(n-1)!, the problem comes when n is large(n = 100). Here as n is large, (n-1)! overflows and becomes 0. In result, I am getting a divide by zero error...any solution or algorithm for that?

Here is my code:

public class KthPermutation {
    public String getPermutation(int n, int k) {
        // initialize all numbers
        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            numberList.add(i);
        }
        int fact = 1;   // set factorial of n-1

        for (int i = 1; i <= n-1; i++) {
            fact = fact * i;
        }   

        if ((long) k > (long) fact * n) {
            k = (int) ((long) k - (long) (fact * n));
        }
        k--; // set k to base 0

        StringBuilder result = new StringBuilder();
        result = getP(result, numberList, n, k, fact);
        return result.toString();
    }
    public static StringBuilder getP(StringBuilder result,
                ArrayList<Integer> numberList, int n, int k, int fact) {    
        if (numberList.size() == 1 || n == 1) {
            result.append(numberList.get(0));
            return result;  // return condition
        }
        int number = (k / fact) + 1 ;
        result.append(numberList.get(number - 1));
        numberList.remove(number - 1);
        k = k % fact;  // update k
        fact = fact / (n - 1);
        n--;
        return getP(result, numberList, n, k, fact);
    }
}

Solution 1

So if I'm reading the question correctly, you want to find the kth permutation, preferrably without using BigIntegers, provided k is not large enough to require a BigInteger.

If we look at the sequence

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

We can rewrite it so that the number in each position is an index into a list of the numbers that haven't appeared so far on the line:

0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0

So for example "2, 0, 0" means start with the list "1, 2, 3", then take the third (because we are indexing from zero), which is a 3, then take the first of the remaining digits "1, 2" which is a 1, then the first of the remaining digit, which is "2". So it produces "3, 1, 2".

To generate these indices, go from right to left and divide k by 1! for the rightmost two places, then 2! then 3! then 4! etc, and then modulo the result with the number of possible indices in that position, which is 1 for the rightmost, 2 for the second-rightmost etc. You don't have to calculate the factorial each time because you can keep a running product.

You can break out of the loop as soon as k divided by the factorial is zero, so you only have to compute factorials up until roughly the size of k multiplied by the last place in which k divided by the factorial is non-zero. If k is too large, you need to switch to BigIntegers.

Once you have the indices it's pretty straightforward to use them to generate the permutation.

Code (k starts from 0, so to find the first pass 0, not 1):

static public void findPermutation(int n, int k)
{
    int[] numbers = new int[n];
    int[] indices = new int[n];

    // initialise the numbers 1, 2, 3...
    for (int i = 0; i < n; i++)
        numbers[i] = i + 1;

    int divisor = 1;
    for (int place = 1; place <= n; place++)
    {
        if((k / divisor) == 0)
            break;  // all the remaining indices will be zero

        // compute the index at that place:
        indices[n-place] = (k / divisor) % place;
        divisor *= place;
    }

    // print out the indices:
    // System.out.println(Arrays.toString(indices));

    // permute the numbers array according to the indices:
    for (int i = 0; i < n; i++)
    {
        int index = indices[i] + i;

        // take the element at index and place it at i, moving the rest up
        if(index != i)
        {
            int temp = numbers[index];
            for(int j = index; j > i; j--)
               numbers[j] = numbers[j-1];
            numbers[i] = temp;
        }
    }

    // print out the permutation:
    System.out.println(Arrays.toString(numbers));
}

Demo

output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

10000000th permutation for n = 100:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 98, 96, 90, 91, 100, 94, 97, 95, 99, 93]

Solution 2

The indices for k'th permutation (used in the answer to this question) are the factoradic representation of k and can be calculated without using factorial or running product.

public static List<Integer> toFactoradic(int x) {
    List<Integer> result = new ArrayList<>();

    for(int i = 1; x > 0; x /= i++) {
        result.add(x % i);
    }

    Collections.reverse(result);
    return result;
}

Of course, the indices array should be padded by 0's from the left so that length of the indices array is equal to number of elements to get the actual indices. Alternatively, the permutation could be applied from the right end.

Solution 3

Of course there is a need for bigints with such an interface

when you have n = 100 then you have n! permutations which means k is in the range k=<1,n!>

100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

which does not fit into the standard unsigned int

2^32=          4294967296
2^64=18446744073709551616

see Fast exact bigint factorial

if you change the interface a bit you suddenly do not need any bigints anymore

just change API so it sequentially returns 1st,2nd,3th,...permutation without specifying k so you need something like:

• Generalized Permutation (without repetitions) in C++

of course this is usable only if your usage of permutation is also sequential. You can also make function previous() to handle algorithms which are almost sequential. For random or non-sequential access you need to use bigints

Solution 4

First we can generate the factoradic reprsentation of k and then use it generate the necessary permutation. Please see https://en.wikipedia.org/wiki/Factorial_number_system for more details.

public String getPermutation(int n, int k) {
    LinkedList<Integer> factoradic = new LinkedList<>();
    k=k-1; // because factoradic representation and its mapping to permutation starts from 0
    for(int i=1;i<=n; i++){ // get radix digits for n digits
        factoradic.addFirst(k%i);
        k=k/i;
    }
    
    //System.out.println(factoradic.size());
    List<Integer> numbers = new LinkedList<>();
    for(int i=1;i<=n;i++){
        numbers.add(i);
    }
    StringBuilder str = new StringBuilder();
    for(int x: factoradic){
        // System.out.println(x);
        str.append(String.valueOf(numbers.get(x)));
        numbers.remove(x);
    }
    return str.toString();
}

View more solutions