如何找到给定字符串及其排名的排列？

Question

例如

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

，如果有人要求我进行 4 级排列，答案是 cab。请给出该程序的java代码

Answer 1

我第一次尝试就成功了！ :-)
非常好的作业，好问题，你让我很开心！这是 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);
}

只需将其称为 permutation(5, 3, ['a', 'b', 'c']) 即可。
你必须编写自己的阶乘（）函数 - 作为家庭作业:-)

Answer 2

这是ac#版本：基本思想是使用阶乘来确定排列，而不是通过尝试获取所有排列（您可以参考我的博客@ 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;
        }

哪里

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

单元测试

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