Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
Wikipedia: Permutation – Generation_in_lexicographic_order
class runner
{
private static void swap(char[] arr, int l, int k){
char tmp = arr[l];
arr[l]=arr[k];
arr[k] = tmp;
}
public static void permutate(char[] arr){
int k = -1;
for(int i=0;i arr[i]) l=i;
}
}
swap(arr,l,k);
int diff = arr.length - (k+1);
for(int i=0; i
Another solution... just dawned on me, after others said there was another way.
import java.util.HashMap;
import java.util.Vector;
class Factorial{
private HashMap store = new HashMap();
int getFactorial(int n)
{
int result = 1;
if(n<=0){return result;}
if(store.containsKey(n)) result = store.get(n);
else result = getFactorial(n-1);
store.put(n, result);
return n*result;
}
}
class runner
{
@SuppressWarnings("serial")
public static void main (String[] args) throws java.lang.Exception
{
long time = System.currentTimeMillis();
int max = 1000000;
Vector arr = new Vector(){
{
add(0);add(1);add(2);add(3);add(4);add(5);add(6);add(7);add(8);add(9);
}
};
Vector output = new Vector();
Factorial obj = new Factorial();
for(int i = arr.size(); i>0; i--){
long split = (long)(obj.getFactorial(i)) / (i);
long j = 0; int count = -1;
do{
j += split;
count ++;
}while( j < max);
max -= split*(count);
output.add(arr.remove(count));
}
System.out.println(output.toString());
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}