**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++) { answer += ""+numbers[i]; } System.out.println("Answer: "+answer); //================================== 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; }

Pingback: Project Euler: Problem 41 – Pandigital prime | Pursuit of Intellectual Curiosity

Pingback: Project Euler: Problem 43 – Sub-string divisibility | Pursuit of Intellectual Curiosity

Pingback: Project Euler: Problem 49 – Prime permutations | Pursuit of Intellectual Curiosity

Pingback: Project Euler: Problem 52 – Permuted multiples | Pursuit of Intellectual Curiosity