# Project Euler: Problem 24 – Lexicographic permutations

#### 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?

#### Idea:

This problem reminded me of a similar problem I encountered at Pacific Lutheran University. I was presented with two options: develop a method to calculate all the permutations and stop at the one I wanted (easier, but inefficient), or given a set, find the next permutation (slightly more difficult, but efficient if you just want to find the next, without having to recalculate all the previous ones). Fearing permutations would arise again in future problems, I went with the latter.

Once the permutation algorithm was handled, the only part that concerned me was: does the first ordering count as the first permutation, or does the second ordering count as the first permutation. Worst case scenario, I’d just have to try submitting 2 answers.

```String answer = "";
int[] numbers = {0,1,2,3,4,5,6,7,8,9};

for(int i = 1; i < 1000000; i++) {
Permutation.nextPermutation(numbers);
}

for(int i = 0; i < numbers.length; i++) {
}

//==================================
public static boolean nextPermutation(int[] array) {
//check for reverse lexicographical order
int index1 = array.length - 2;
while (index1 >= 0 && array[index1] >= array[index1 + 1]) {
index1--;
}

//if in reverse lexicographical order, no more permutations
if (index1 == -1) {
return false;
}

//find first element from the end
//that's greater than the element from above
int index2 = array.length - 1;
while (array[index2] <= array[index1]) {
index2--;
}

//swap those elements;
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;

//reverse the remaining elements to complete
//the next lexicographical permutation
for (int i = index1 + 1, j = array.length - 1; i < j; i++, j--) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
return true;
}```