Sunday, March 9, 2014

Problem 24: Lexicographic permutations

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?

Solution:
One of the most easiest problems till now, All you've to do is take the numbers into a string, generate all possible permutations, store them in an array, and sort the array, and then find the permutation stored at the millionth position.

The java code:


import java.util.ArrayList;
import java.util.Collections;

public class Prob24 {
static ArrayList<Long≫ numPermutations = new ArrayList<Long≫();

public static void main(String args[]) {
System.out.println();
permutation("","0123456789");
Collections.sort(numPermutations);
System.out.println(numPermutations.get(1000000-1)); 
}


private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) 
    {
     numPermutations.add(Long.parseLong(prefix));
    }
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}
 
 
}