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

Question

例如，

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

所以，如果有人问我第四个排列是什么，答案是cab。请提供此程序的java代码。

- Alkesh Patel

---

你好，欢迎来到SO！这里的人们很乐意提供帮助，但必须要看到你付出了一些努力：很多人会愿意帮你解决一个具体的问题，但不会同意直接给你代码。 - Pascal MARTIN

我猜这是一份作业吧？至少试着解决它，提供你已经拥有的。 - Michael

你们的评价是正确的，但这确实是一个非常有趣的问题！好作业！+1！请不要关闭它，因为它真的很有趣。 - Tomas

https://dev59.com/JlnUa4cB1Zd3GeqPa31l - Karoly Horvath

在SO上，“请给我代码”的问题是不受欢迎的。 - hugomg

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']) 就可以了。 你需要自己编写阶乘函数 - 这是一项作业 :-)

- Tomas

---

但是算法就是算法 :-) 语言只是一个小细节，也可以像作业一样解决 :-) - Tomas

Answer 2

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

- Dreamer