In this article, we will learn how to create permutations of a string in C#. By permutating characters, we can generate different words from the same characters.
So, let’s start.
Permutations With Repetitions
In our article about permutations, we discussed permutating elements without repetitions. We permutated elements like [1, 2, 3] into six possible arrangements [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1]. However, we failed to consider the potential for repeating elements since permutations in their purest form always exclude repetitions.
Nevertheless, what if we want to permutate characters in a word to see if we can construct some other word from the same letters? What if we wish to permutate letters from the word “banana”? There are six letters, so we would expect 6! (=720) permutations, but in reality, many would be the same. Because we have repeating letters – the letter ‘a’ is found three times and the letter ‘n’ twice – we can construct only 60 different strings, not 720.
Sixty different strings from letters ‘b’, ‘a’, ‘n’, ‘a’, ‘n’, and ‘a’ would be too much to display here, so let’s instead construct all possible strings from the word ‘ulu‘. If we write out all permutations, we will get the following: ‘ulu’, ‘uul’, ‘luu’, ‘luu’, ‘uul’, ‘ulu’. We can see that there are only three distinct strings: ‘ulu’, ‘uul’, and ‘luu’.
Number of Permutations With Repetitions
In the aforementioned article, we derived a formula for calculating the number of distinct permutations of N elements as N!, representing the product of all numbers from 1 to N, i.e., 1*2*3*…*(N-1)*N.
We won’t delve into the details here, as this article primarily focuses on algorithms rather than mathematics. However, we can easily find information about this formula online, so for our purposes, we will just provide it along with a brief summary of its logic.
Suppose we have N elements: the first element repeated M1 times, the second repeated M2 times, and the third repeated M3 times. We can calculate the number of different permutations with the formula N! / (M1! * M2! * M3!).
In the case of ‘banana’, we have 6 (N) letters, with the letter ‘a’ repeated three (M1) times and the letter ‘n’ repeated two (M2) times. Therefore, we have 6! / (3! * 2!) permutations, which equals 720 / (6 * 2) = 60 different strings.
A Small Problem
By employing any of the permutation generation algorithms mentioned in the preceding article, we would end up producing an excessive number of strings. Additionally, we would need to store all the results and verify whether we have already generated an identical string.
This is not the path we want to take, so we have to find another algorithm for generating permutations.
Fortunately for us, we don’t have to invent anything new. Indian mathematician Narayana Pandita invented the algorithm in the 14th century.
The algorithm is concise, elegant, and easy to write. We can find it on the internet, but the description and the logic behind it can be hard to find. So we will discuss this first and then write it in C#.
Pandita’s Algorithm
It is easy to envision that a mathematician from the 14th century did not have access to computers or the ability to write programs. Furthermore, their focus was likely on contemplating numbers rather than words. So his question was: “Which is the next bigger number that I can construct from some given digits?“.
Suppose we have some number 56,786,975. What is the next smallest number we can generate, and how would we generate it?
Arranging the digits in ascending order results in the smallest number possible, whereas sorting them in descending order yields the largest possible number.
We have the digits 5, 6, 7, 8, 6, 9, 7, and 9. Suppose we sort them like 5, 6, 6, 7, 7, 8, 9, and 9; we will get 56,677,899, the smallest possible number. But sorted the other way around: 9, 9, 8, 7, 7, 6, 6, and 5, we will get the biggest possible number, or 99,877,665.
Path to Next Permutation
How does this help us find the next smallest number after 56,786,975? If we look from the right, we see that the digits at the end, ‘975’ are already sorted in descending order, so they are ok. The previous digit is 6.
Now we have 6,975, and we need to replace the digit 6 with one of 9, 7, or 5. We can generate 9,675, 7,965, or 5,976. 7 is the right answer, as 9 is too big and 5 is too small. So we have 7,965. Is this the next biggest number, or is there a smaller one?
Digits 9, 6, and 5 are in descending order. If we sort them in ascending order, we will get a smaller number: 7,569. And by appending other digits, we will get the correct answer for the next biggest number or next permutation: 56,787,569.
Pandita’s Algorithm in Plain English
From this short example and an intense mental workout, perhaps we could have arrived at the same algorithm as Narayana Pandita did 600 years ago:
- Begin by starting from the rightmost element of the sequence and locate the first element smaller than the element to its right. That was the digit 6 in our example. Let’s label this element
i. - If we can’t find such an element
i, then we have found the greatest permutation and can exit. - Now we have to identify the smallest element to the right of
ithat is larger thani. That was the digit 7 in our example. Let’s denote this element asj. - Swap the elements
iandj. - Reverse the elements to the right of the position of
i. - This is the next lexicographically ordered permutation.
Pandita’s Algorithm in C#
In recent versions of .NET, a specialized class called Span has been introduced to facilitate working with characters within a string. By following the text of the algorithm, we can easily write a C# method called NextPermutation:
public bool NextPermutation(Span<char> input)
{
int i = input.Length - 2;
while (i >= 0 && input[i] >= input[i + 1])
{
i--;
}
if (i < 0)
return false;
int j = input.Length - 1;
while (input[j] <= input[i])
{
j--;
}
(input[i], input[j]) = (input[j], input[i]);
Reverse(input, i + 1);
return true;
}
This is the exact C# implementation of the plain English description of the algorithm. All we have to do is write a Reverse method:
private void Reverse(Span<char> input, int start)
{
int i = start;
int j = input.Length - 1;
while (i < j)
{
(input[i], input[j]) = (input[j], input[i]);
i++;
j--;
}
}
That is the whole algorithm, and with these helper methods, we can easily write a method for generating all possible permutations of a string:
private List<string> GeneratePermutations(string input)
{
var array = input.ToCharArray().OrderBy(c => c).ToArray();
Span<char> spanInput = array.AsSpan();
var result = new List<string>() { new string(spanInput) };
while (NextPermutation(spanInput))
result.Add(new string(spanInput));
return result;
}
In line 3 we have to sort the characters so we can start the algorithm with the smallest permutation. And in line 6 we can already add the first permutation.
Comparing Heaps And Pandita’s Algorithms
How does this new, Pandita’s algorithm compare with the Heaps algorithm we developed in our earlier article? To answer this question, we have to benchmark them:
[MemoryDiagnoser]
public class MemoryAlgorithmsBenchmark
{
[Params(4, 6, 8, 10)]
public byte NumberOfItems;
[Benchmark]
public void PanditasAlgorithmBenchmark()
{
IPermutation algorithm = new PanditasAlgorithm();
algorithm.BenchmarkPermutations(NumberOfItems);
}
[Benchmark]
public void HeapsAlgorithmBenchmark()
{
IPermutation algorithm = new HeapsAlgorithm();
algorithm.BenchmarkPermutations(NumberOfItems);
}
}
The results of our testing on a typical modern desktop computer are:
| Method | Items | Mean | Allocated | |------------------ |------ |-----------------|-----------| | HeapsAlgorithm | 4 | 194.2 ns | 56 B | | PanditasAlgorithm | 4 | 327.9 ns | 144 B | | HeapsAlgorithm | 6 | 5,420.4 ns | 56 B | | PanditasAlgorithm | 6 | 6,458.0 ns | 144 B | | HeapsAlgorithm | 8 | 309,548.4 ns | 56 B | | PanditasAlgorithm | 8 | 355,826.6 ns | 144 B | | HeapsAlgorithm | 10 | 27,297,065.8 ns | 75 B | | PanditasAlgorithm | 10 | 32,077,441.2 ns | 190 B |
The table demonstrates that the Heaps algorithm is faster, but the difference in speed is not significant. Also, Heap’s algorithm will produce the same permutations if there are repeating elements in the set, so it is not suitable for permuting characters in strings.
Conclusion
When permutating a string with repeated elements, employing an algorithm designed to handle such cases is crucial. The Pandita algorithm stands out as the top choice due to its exceptional speed, surpassing even the fastest Heaps algorithm.
One notable advantage of the Pandita algorithm is its non-recursive nature. It can instantly generate the next permutation without relying on recursive calls. As a result, this algorithm is widely employed in various standard libraries to implement the nextPermutation method.
