Problem 24

Problem Statement :Problem24

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?

Approach:

• Well if the actual number  is a0,a1,a2,a3,a4,a5,a6,a7,a8,a9:
  a0*9! + a1*8! + a2*7! + ..... + a9*0! = 10^6 
• To do this start filling the number from the right 
• In every iteration decide the digit at that position and subtract the remaining from count.
• In each iteration we are removing multiples of k! 
• Quit when count reaches 0.  

Solution:

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

public class problem24 {
 public static List list = new ArrayList();
 
 public static long getFactorial(int limit) {
  long factorial = 1;
  for (int i = 1; i <= limit; i++)
   factorial = factorial * i;
  return factorial;
 }

 public static void main(String chars[]) {
  long count = 1000000;
  int num = 9;
  list.add(0);
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  list.add(5);
  list.add(6);
  list.add(7);
  list.add(8);
  list.add(9);
  
  String s = "";
  while (count != 0) {
   long fact = getFactorial(num--);
   int p1 = (int) (count / fact);
   s=s+""+list.get(p1);
   list.remove(p1);
   count = count - fact * p1;
  }
 System.out.println(s+list.get(0));
 }
}