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++) {
   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;
}
Bookmark the permalink.