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