Sunday, February 5, 2012

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

No comments:

Post a Comment