# 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;
}
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];