package euler;

/**

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?

*/

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Problem24 {

    public static void main(String[] args) {
        solve();
    }

    /**
     * Solver
     */
    private static void solve() {

        // Observation.
        //
        // Given a set of k digits, the first factorial(k-1) permutations will
        // begin with the smallest digit in that set.
        //

        // Let 'digits' be a list of candidate digits.
        List<Integer> digits = new ArrayList<Integer>();
        for (int i = 0; i <= 9; ++i) {
            digits.add(new Integer(i));
        }

        // Let 'solution' be a list of digits in the order of our solution.
        List<Integer> solution = new ArrayList<Integer>();

        // We need to track the number of permutations we have "seen".
        int numSeen = 0;

        // And we need a target permutation.
        int targetPermutation = 1000000;

        // Since we want the targetPermutation'th, the targetSeen is that -1.
        int targetSeen = targetPermutation - 1;

        // How long should we run for? Put it this way. A solution permutation
        // must contain all of the digits. Thus the following loop must execute
        // until the list of digits is empty.
        //
        // While there are digits...
        while (!digits.isEmpty()) {
            int k = digits.size();
            int f = factorial(k-1);
            int gap = targetSeen - numSeen;
            int i = gap / f;
            System.out.println(String.format(
                "k: %d, f: %d, gap: %d, i: %d, numSeen: %d",
                k, f, gap, i, numSeen));
            solution.add(digits.remove(i));
            numSeen += i * f;
        }

        StringBuilder sb = new StringBuilder();
        for (Integer i : solution) {
            sb.append(i);
        }
        System.out.println("ans: " + sb.toString());
    }

    private static int factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Bad arg, n is " + n);
        }
        int result = 1;
        for (int i = 1; i <= n; ++i) {
            result *= i;
        }
        return result;
    }
}

@@ -9,16 +9,47 @@
 euler;%0A%0A
+// Solution posted on page 8.%0A%0A
 /**%0A%0ALex
@@ -552,38 +552,8 @@
 ist;
-%0Aimport java.util.Collections;
 %0A%0Apu
@@ -629,22 +629,202 @@
         
-solve(
+long t0 = System.currentTimeMillis();%0A        solve();%0A        long t1 = System.currentTimeMillis();%0A        long elapsed = t1 - t0;%0A        System.out.println(%22elapsed msec: %22 + elapsed
 );%0A    %7D
@@ -2159,24 +2159,27 @@
 %0A           
+ //
  System.out.
@@ -2208,24 +2208,27 @@
 %0A           
+ //
      %22k: %25d,
@@ -2272,24 +2272,27 @@
 %0A           
+ //
      k, f, g
@@ -2613,24 +2613,59 @@
 al(int n) %7B%0A
+        // Note: factorial 0 is 1.%0A
         if (

Add timing calls to Java solution of Problem 24