a Programmer's blog

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));
	}
}