PROBLEM STATEMENT
Create a method that takes two arguments, a word, and an index into the list of
unique letter arrangements of the word, ordered alphabetically, that can be
produced using all of the letters in the original word. Each arrangement will
be the same length as the original word. The word may contain duplicate
letters. The index is zero based. If the index is greater than the highest
index in the alphabetized list of words, the method returns the empty string.
DEFINITION
Class Name: Permutations
Method Name: permutation
Parameters: String, int
Returns: String
Method signature (be sure your method is public): String permutation(String
word, int arrangement);
TopCoder will ensure the following:
- word consists only of the twelve lowercase letters "abcdefghijkl"
- word is 1 to 12 characters in length, inclusive
- arrangement is between 0 and 500000000 inclusive
HINT
COUNTING PERMUTATIONS OF MULTISETS
Suppose that a set of n objects is partitioned into subsets of k different
types, with n1, n2, ... , nk members, so that n = n1+n2+...+nk. Regard two
permutations of the set as distinguishable in case their entries in at least
one position are of different types. Then there are:
(n!)/(n1! * n2! * ... * nk!) distinguishable permutations of the set.
The ! symbol is factorial which is used to represent the product of all
integers from 1 to n inclusive. For example, 4! = 1 * 2 * 3 * 4 = 24.
And so, given the string "cab" there are 3! possible arrangements, 3 being the
length of the string "abc". There is 1 'c', 1 'a', and 1 'b' in the string. And
so using the formula above, the number of unique arrangements of "cab" is equal
to (3!)/(1!*1!*1!) = 6/1 = 6.
The string baabbb has length 6 and contains 2 'a' and 4 'b' letters. Thus, the
number of unique arrangements is (6!)/(2!*4!) = 720/48 = 15.
EXAMPLES
Given the word "cab", there are six possible unique arrangements. In
alphabetical order the six arrangements are "abc", "acb", "bac", "bca", "cab",
"cba".
permutation("cab", 0) ==> "abc"
permutation("cab", 1) ==> "acb"
permutation("cab", 2) ==> "bac"
permutation("cab", 3) ==> "bca"
permutation("cab", 4) ==> "cab"
permutation("cab", 5) ==> "cba"
permutation("cab", 6) ==> ""
Given the word "baa", there are three possible unique arrangements. In
alphabetical order the three arrangements are "aab", "aba", "baa".
permutation("baa", 0) ==> "aab"
permutation("baa", 1) ==> "aba"
permutation("baa", 2) ==> "baa"
permutation("baa", 3) ==> ""
More Examples
permutation("aaa", 0) ==> "aaa"
permutation("aaa", 1) ==> ""
permutation("alll", 2) ==> "llal"
permutation("abcde", 26) ==> "badce"
permutation("baabbb", 11) ==> "bbabba"