How to find permutation of a given string with its rank?

Question

For example,

rank  permutation   
0     abc
1     acb
2     bac
3     bca
4     cab
5     cba

So, if one asks give me permutation with rank 4, the answer is cab. Pls give the java code for this program

Answer 1

Here is a c# version: basic idea is to using factorial to determine the permutation, rather than by trying to get all the permutations (you may refer to my blog @ http://codingworkout.blogspot.com/2014/08/kth-permutation.html)

public string GetKthPermutation(string s, int k, int[] factorial)
        {
            if (k == 1)
            {
                return s;
            }
            Assert.IsTrue(k > 1);
            int numbeOfPermutationsWithRemainingElements = factorial[s.Length-1];
            string permutation = null;
            if (k <= numbeOfPermutationsWithRemainingElements)
            {
                //just find the kthPermutation using remaining elements
                permutation = s[0] + this.GetKthPermutation(s.Substring(1), k, 
                    factorial);
                return permutation;
            }
            int quotient = k / numbeOfPermutationsWithRemainingElements;
            int remainder = k % numbeOfPermutationsWithRemainingElements;
            Assert.IsTrue(quotient > 0);
            int indexOfCurrentCharacter = quotient;
            if(remainder == 0)
            {
                indexOfCurrentCharacter -= 1;
            }
            permutation = s[indexOfCurrentCharacter].ToString();
            Assert.IsTrue(indexOfCurrentCharacter > 0);
            Assert.IsTrue(indexOfCurrentCharacter < s.Length);
            string remainingCharactersString = s.Substring(0, indexOfCurrentCharacter);
            if(indexOfCurrentCharacter < (s.Length-1))
            {
                remainingCharactersString += s.Substring(indexOfCurrentCharacter + 1);
            }
            if(remainder == 0)
            {
                k = numbeOfPermutationsWithRemainingElements;
            }
            else
            {
                k = remainder;
            }
            permutation += this.GetKthPermutation(remainingCharactersString, k, factorial);
            return permutation;
        }

where

public string GetKthPermutation(string s, int k)
        {
            s.ThrowIfNullOrWhiteSpace("a");
            k.Throw("k", ik => ik <= 0);
            int[] factorial = new int[s.Length+1];
            factorial[0] = 0;
            factorial[1] = 1;
            for(int i =2;i<=s.Length; i++)
            {
                factorial[i] = factorial[i - 1] * i;
            }
            if(k > factorial[s.Length])
            {
                throw new Exception(string.Format("There will be no '{0}' permuation as the total number of permutations that can be abieved are '{1}'", k, s.Length));
            }
            string kthPermutation = this.GetKthPermutation(s, k, factorial);
            return kthPermutation;
        }

Unit Test

[TestMethod]
        public void KthPermutationTests()
        {
            string s1 = "abc";
            string[] perms1 = { "abc", "acb", "bac", "bca", "cab", "cba"};
            for(int i =1;i<=6;i++)
            {
                string s = this.GetKthPermutation(s1, i);
                Assert.AreEqual(s, perms1[i - 1]);
                string ss = this.GetKthPermutation_BruteForce(s1, i);
                Assert.AreEqual(ss, s);
            }
            s1 = "123";
            perms1 = new string[] {"123", "132", "213", "231", "312", "321"};
            for (int i = 1; i <= 6; i++)
            {
                string s = this.GetKthPermutation(s1, i);
                Assert.AreEqual(s, perms1[i - 1]);
                string ss = this.GetKthPermutation_BruteForce(s1, i);
                Assert.AreEqual(ss, s);
            }
            s1 = "1234";
            perms1 = new string[] { "1234", "1243", "1324", "1342", "1423", "1432", 
                                    "2134", "2143", "2314", "2341", "2413", "2431",
                                    "3124", "3142", "3214", "3241", "3412", "3421",
                                    "4123", "4132", "4213", "4231", "4312", "4321"};
            for (int i = 1; i <= 24; i++)
            {
                string s = this.GetKthPermutation(s1, i);
                Assert.AreEqual(s, perms1[i - 1]);
                string ss = this.GetKthPermutation_BruteForce(s1, i);
                Assert.AreEqual(ss, s);
            }
        }

Answer 2

I made it at a first attempt!! :-) Really good homework, nice problem, you made my day! Here is a solution in javascript:

function permutation (rank, n, chars) 
{
    var fact, char_idx, this_char;

    if (n == 0)
        return "";

    char_idx = Math.floor(rank / factorial(n - 1));

    this_char = chars.splice(char_idx, 1); 
         // returns the char with index char_idx and removes it from array

    return this_char + 
        permutation(rank % factorial(n - 1), n - 1, chars);
}

Just call it like permutation(5, 3, ['a', 'b', 'c']) and that's it. You have to write your own factorial() function - as a homework :-)