Kth Permutation

Given a string or collection of elements, find the kth permutation of them. For ex, if "123" is the given string then following are their permutations in order: "123", "132", "213", "231", "312", "321".

 

One obvious way to solve the problem is by enumerating all the permutations and eventually stopping when we get to the requested permutation. The approach is brute force as in the worst case it takes up-to O(n!) - for ex, if the requested permutation is n!th one or >n!.

 

Problem can be solved if we skip enumerating all permutations, and get to the required one by using factorials. Below is the corresponding code for the same. I have also posted the brute force one for convenience.

Optimal Approach (O(N))

Code Snippet

58. public string GetKthPermutation(string s, int k)
59.         {
60.             s.ThrowIfNullOrWhiteSpace("a");
61.             k.Throw("k", ik => ik <= 0);
62.             int[] factorial = new int[s.Length+1];
63.             factorial[0] = 0;
64.             factorial[1] = 1;
65.             for(int i =2;i<=s.Length; i++)
66.             {
67.                 factorial[i] = factorial[i - 1] * i;
68.             }
69.             if(k > factorial[s.Length])
70.             {
71.                 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));
72.             }
73.             string kthPermutation = this.GetKthPermutation(s, k, factorial);
74.             return kthPermutation;
75.         }
76.         public string GetKthPermutation(string s, int k, int[] factorial)
77.         {
78.             if (k == 1)
79.             {
80.                 return s;
81.             }
82.             Assert.IsTrue(k > 1);
83.             int numbeOfPermutationsWithRemainingElements = factorial[s.Length-1];
84.             string permutation = null;
85.             if (k <= numbeOfPermutationsWithRemainingElements)
86.             {
87.                 //just find the kthPermutation using remaining elements
88.                 permutation = s[0] + this.GetKthPermutation(s.Substring(1), k,
89.                     factorial);
90.                 return permutation;
91.             }
92.             int quotient = k / numbeOfPermutationsWithRemainingElements;
93.             int remainder = k % numbeOfPermutationsWithRemainingElements;
94.             Assert.IsTrue(quotient > 0);
95.             int indexOfCurrentCharacter = quotient;
96.             if(remainder == 0)
97.             {
98.                 indexOfCurrentCharacter -= 1;
99.             }
100.             permutation = s[indexOfCurrentCharacter].ToString();
101.             Assert.IsTrue(indexOfCurrentCharacter > 0);
102.             Assert.IsTrue(indexOfCurrentCharacter < s.Length);
103.             string remainingCharactersString = s.Substring(0, indexOfCurrentCharacter);
104.             if(indexOfCurrentCharacter < (s.Length-1))
105.             {
106.                 remainingCharactersString += s.Substring(indexOfCurrentCharacter + 1);
107.             }
108.             if(remainder == 0)
109.             {
110.                 k = numbeOfPermutationsWithRemainingElements;
111.             }
112.             else
113.             {
114.                 k = remainder;
115.             }
116.             permutation += this.GetKthPermutation(remainingCharactersString, k, factorial);
117.             return permutation;
118.         }

Brute Force

Code Snippet

14. public string GetKthPermutation_BruteForce(string s, int k)
15.         {
16.             s.ThrowIfNullOrWhiteSpace("a");
17.             k.Throw("k", ik => ik <= 0);
18.             int count = 0;
19.             var permutation = this.GetKthPermutation_BruteForce(s, "", k, ref count);
20.             if(!string.IsNullOrEmpty(permutation))
21.             {
22.                 Assert.AreEqual(count, k);
23.             }
24.             return permutation;
25.         }
26.         private string GetKthPermutation_BruteForce(string input, string prefixOfPermutation, int k,
27.             ref int count)
28.         {
29.             if (input.Length == 0)
30.             {
31.                 count++;
32.                 if(count == k)
33.                 {
34.                     return prefixOfPermutation;
35.                 }
36.                 return null;
37.             }
38.             for (int i = 0; i < input.Length; i++)
39.             {
40.                 string recursiveCallInput = "";
41.                 if (i != 0)
42.                 {
43.                     recursiveCallInput = input.Substring(0, i);
44.                 }
45.                 if (i < input.Length - 1)
46.                 {
47.                     recursiveCallInput += input.Substring(i + 1);
48.                 }
49.                 string prefix = prefixOfPermutation + input[i];
50.                 var permutation = this.GetKthPermutation_BruteForce(recursiveCallInput, prefix, k, ref count);
51.                 if(null != permutation)
52.                 {
53.                     return permutation;
54.                 }
55.             }
56.             return null;
57.         }

Unit Tests

Code Snippet

119. [TestCategory(Constants.PermutationsAndCombinations)]
120.         [TestMethod]
121.         public void KthPermutationTests()
122.         {
123.             string s1 = "abc";
124.             string[] perms1 = { "abc", "acb", "bac", "bca", "cab", "cba"};
125.             for(int i =1;i<=6;i++)
126.             {
127.                 string s = this.GetKthPermutation(s1, i);
128.                 Assert.AreEqual(s, perms1[i - 1]);
129.                 string ss = this.GetKthPermutation_BruteForce(s1, i);
130.                 Assert.AreEqual(ss, s);
131.             }
132.             s1 = "123";
133.             perms1 = new string[] {"123", "132", "213", "231", "312", "321"};
134.             for (int i = 1; i <= 6; i++)
135.             {
136.                 string s = this.GetKthPermutation(s1, i);
137.                 Assert.AreEqual(s, perms1[i - 1]);
138.                 string ss = this.GetKthPermutation_BruteForce(s1, i);
139.                 Assert.AreEqual(ss, s);
140.             }
141.             s1 = "1234";
142.             perms1 = new string[] { "1234", "1243", "1324", "1342", "1423", "1432",
143.                                     "2134", "2143", "2314", "2341", "2413", "2431",
144.                                     "3124", "3142", "3214", "3241", "3412", "3421",
145.                                     "4123", "4132", "4213", "4231", "4312", "4321"};
146.             for (int i = 1; i <= 24; i++)
147.             {
148.                 string s = this.GetKthPermutation(s1, i);
149.                 Assert.AreEqual(s, perms1[i - 1]);
150.                 string ss = this.GetKthPermutation_BruteForce(s1, i);
151.                 Assert.AreEqual(ss, s);
152.             }
153.         }