Need explanation on differences of permutation algorithms

Question

I'm currently working on a problem that asks me to find the millionth lexicographic permutation of 0,1,2,3,4,5,6,7,8,9. I thought of a very crude solution at first glance that had a complexity of around O(n^3)

    public static String permute(char[] a){
        ArrayList<String> array = new ArrayList<String>(); 
        int counter = 1; 
        for (int i = 0; i < a.length; i++){
            array[counter] += a[i];
            for (int j = 0; j < i; j++){
            array[counter] += a[j];
                for(int k = a.length; k > i; k--){
                array[counter] += a[k];}counter++;}
        }
    }

The code may not be perfect but the idea is that a single digit is selected and then moves to the end of an array. The second array creates the numbers behind the selected digit and the third array creates numbers after it. This seems like a terrible algorithm and i remembered a past algorithm that's like this.

    public static HashSet<String> Permute(String toPermute) {
        HashSet<String> set = new HashSet<String>();
        if (toPermute.length() <= 1 )
            set.add(toPermute);
        else {
            for (int i = 0; i < toPermute.length(); i++ )
                for (String s: Permute(toPermute.substring(0,i)+ toPermute.substring(i+1)))
                {
                    set.add(toPermute.substring(i,i+1)+s);}
        }
        return set;
    }

}

The problem is that this algorithm uses unordered sets and I have no idea about how it can become ordered enough for me to find the millionth permutation. I also do not know the complexity other than the fact it could be O(n^2) because it calls itself n times and then unstacks.

Answer 1

It seems to me (1) which permutation is the millionth depends absolutely on the order you use, and (2) permutations of this sort are ripe problems for recursion. I would write this as a recursive program and increment the count for each iteration. [was that your question? I didn't really see a question...]

Answer 2

A couple of things in general about your code above:

1. You should implement to interfaces and not concrete classes I.e. List<String> array = .... Similarly with your Set.
2. Array's start at index 0, you are starting your counter at index 1.

Finally to answer your question there is a brute force way and a more elegant way that uses some principles in math. Have a look at this site which explains the approaches.

Answer 3

Here is a solution that is more efficient:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P24 {

    static final int digits[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static List<Integer> remainedDigits = new ArrayList(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
    static final int factorials[] = new int[digits.length + 1];
    static final int N = 1000_000;

    static int low = -1;
    static int lowIndex = -1;
    static int highIndex = -1;

    public static void main(String args[]) {
        populateFactorials(digits.length);
        validateN(N);
        identifyMargins();
        int n = N;  // it will be changed

        int fixedDigits = digits.length - highIndex;

        String result = "";
        for (int i = 0; i < fixedDigits; i++) {
            result += remainedDigits.get(0);
            remainedDigits.remove(0);
        }

        for (int i = fixedDigits; i < digits.length; i++) {
            int pos = 0;
            int firstDigit = remainedDigits.get(pos);
            low = factorials[lowIndex];
            while (n - low > 0) {
                pos++;
                n -= low;
            }
            lowIndex--;
            result += remainedDigits.get(pos);
            remainedDigits.remove(pos);
        }

        System.out.println(result);
    }

    private static void validateN(int n) {
        if (n < 0 || n > factorials[factorials.length - 1]) {
            System.out.println("The input number is not valid");
            System.exit(0);
        }
    }

    private static void identifyMargins() {
        for (int i = 0; i < factorials.length - 1; i++) {
            if (factorials[i] <= N && N < factorials[i + 1]) {
                lowIndex = i;
                highIndex = i + 1;
            }
        }
    }

    private static void populateFactorials(int max) {
        for (int i = 0; i <= max; i++) {
            factorials[i] = fact(i);
        }
    }

    private static int fact(int x) {
        if (x == 0 || x == 1) {
            return 1;
        }
        int p = 1;
        for (int i = 2; i <= x; i++) {
            p *= i;
        }
        return p;
    }

}

Time: 305 microseconds.

Explanation:

1. Because the total number of permutations for {a1, ..., an} is n!, I decided that I need a factorials array. I stored in it: {0!, ..., 10!}.
2. I identified where is the number placed in this sequence, and for our case (N = 1000000) it is between 9! and 10!. If it was lower than 9! I add a padding of fixedDigits digits taken from the remainedDigits array.
3. Because the number is bigger than 9!, I count how many times I can extract 9! from the number and the result helps me to obtain the first digit. Then, I have a similar approach for 8!, 7!, etc.

The above explanation is based on the following simple observation. If we have a set {a1,...,ai,...,an} and we fix a1, ..., ai, we can obtain (n-i)! different strings.

---

Notice that if you use:

static List<Integer> remainedDigits = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

you cannot remove elements from the list. `