My code:
package beust.codingchallenge;
/**
* Challenge: http://beust.com/weblog/archives/000491.html
*
* Theory: It is the number of permutations of K objects from a set of N objects.
* Usually written as nPk = n!/(n-k)!
*
* @author Thierry Janaudy - thierry@janaudy.com
*/
public final class Challenge {
/**
* In the formula above, represents the set of n objects: 0, 1, 2, ..., 9
*/
private static final int n = 10;
/**
* Number
*/
private int count = 0;
/**
* Challenge
*/
public Challenge() {
final long t0 = System.currentTimeMillis();
for(int k=1; k <= 4; k++) { // k represents the max (10 = 1, 100 = 2, ...)
// System.out.println("-----------------");
solve(k);
}
final long tf = System.currentTimeMillis() - t0;
System.out.println("Total number of numbers: " + count);
System.out.println("Done in " + tf + " ms");
}
/**
* @param select
*/
private void solve(int select) {
final int[] value = new int[select];
final int[] array = new int[select];
for(int i=0; i < select; i++)
array[i] = i + 1;
while(true) {
for(int n=0; n < select; n++)
value[n] = array[n];
output(value, select);
while(nextPermutation(value, select)) output(value, select);
int i = select - 1;
while (i >= 0 && array[i] == (n - select + i + 1))
--i;
if (i < 0) break;
++array[i];
for (int j = i + 1; j < select; j++)
array[j] = array[i] + j - i;
} // while
}
/**
* @param k
* @return
*/
private boolean nextPermutation(int[] val, int k) {
int i = k - 1;
if (i <= 0)
return false;
while(i > 0 && val[i-1] >= val[i])
i--;
if (i < 1)
return false;
int j = k;
while(val[j-1] <= val[i-1])
j--;
swap(val, i-1, j-1);
i++;
j = k;
while(i < j) {
swap(val, i-1, j-1);
i++;
j--;
}
return true;
}
/**
* @param val
* @param a
* @param b
*/
private void swap(int[] val, int a, int b) {
int tmp = val[a];
val[a] = val[b];
val[b] = tmp;
}
/**
* @param val
* @param k
*/
private void output(int[] val, int k) {
if (val[0] == 10) return;
for(int i=0; i < k; i++) {
// System.out.print(" "+val[i]);
}
// System.out.println();
count++;
}
/**
* @param args
*/
public static void main(String[] args) {
new Challenge();
}
}
For N = 10,000, 5,274 is found in 2 ms
For N = 10,000,000,000, 8,877,690 is found in 700 ms or so.
