Euler Problem 24

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This one was interesting because there are a number of algorithms out there for listing permutations. The two main choices are recursive and iterative. Both work but …

I tried recursive first as it looks simple, but ran into problems. Recursive routines might look elegant and simple, but they are slow and resource hogs because of stack management overhead. I had to boost my stack to 512M from 128M to avoid a crash and it took over 3 minutes to run. Not the most efficient solution. Plus the resulting list needs to be sorted. Bad.

Then I tried iterative — found one that was already lexicographic, so I didn’t need to sort anything. The routine looks a little more complicated, but it doesn’t need any more stack than default and it runs in 4 seconds. Better.

import java.util.*;

public class Euler24
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 24:\n”);
        Euler24 e = new Euler24();
        System.out.print(“Answer = ” + e.Problem1()+ “\n”);
    }
    public String Problem1 ()
    {
        ArrayList<String> P = new ArrayList<String>();
        int N = 10;
        String num = “”;
        int [] val = new int [N];
        for (int i = 0; i < N; i++)
        {
            val[i] = i;
            num += i;
        }
        P.add(num);
        while (P.size() <= 1000000)
        {
            int i = N – 1;
            while (val[i-1] >= val[i])
                i = i-1;
            int j = N;
            while (val[j-1] <= val[i-1])
                j = j-1;
            val = swap (val, i, j);
            i++;
            j = N;
            while (i < j)
            {
                val = swap (val, i, j);
                i++;
                j–;
            }
            num = “”;
            for (int n = 0; n < N; n++)
                num += val[n];
            P.add(num);
        }
        return String.valueOf(P.get(999999));
    }
    public int [] swap (int [] val, int i, int j)
    {
        int temp = val[i-1];
        val[i-1] = val[j-1];
        val[j-1] = temp;
        return val;
    }
}