In this article, we will examine the world of algorithms. Specifically, we will talk about an algorithm that we can use to generate permutations.
Let’s start.
Permutations
Firstly, we need a definition for permutation, of which there are a few. Even Wikipedia’s definition is quite difficult to understand. Therefore, let us say that a permutation is an arrangement of items in a particular order, with the order being paramount.
To dive in a little further, let’s examine a concrete example. Let us say that we have three coins (1, 2, and 5 cents). What are the different possibilities for arranging these coins? It turns out that there are six possible arrangements: [1, 2, 5], [1, 5, 2], [2, 1, 5], [2, 5, 1], [5, 1, 2], [5, 2, 1]. This is the set of all possible permutations of 3 items.
Number of Permutations
Before moving on to programming, let us answer a theoretical question: “How many possible permutations are there for N items?’. We already saw that there are six possibilities when we have three items.
We have N options for the first position if we have N items. Then we only have N-1 items for the second position, as we already used 1 for the first position. On the third position, we have N-2 items, and so on. With that, we can deduce a formula as N * (N-1) * (N-2) * … * 3 * 2 * 1, which is a mathematical definition for factorial, and the symbol for factorial is an exclamation mark (!).
The number of all possible permutations on N items is N!, which can quickly become very large. For example, with three items, there are six permutations. Moreover, if we have six items, there are already 720 permutations. Similarly, with ten items, there are 3,628,800 permutations; with 20 items, there are whooping 2,432,902,008,176,640,000 permutations.
To put this into perspective, suppose we have a printer so fast that it can print 1000 permutations in one second. That printer would print all permutations of the 20 elements for about 77 million years. Keeping that in mind, we’ll want to use an algorithm as fast as possible.
How Excellent and Quick Is an Algorithm? The Big O Notation.
In the field of combinatorics and algorithms, determining an algorithm’s quality is crucial. We need to classify whether algorithm A is better than algorithm B. The “Big O” notation is a special notation in computer science that helps determine the upper bound of the number of calculations an algorithm must execute to achieve a result.
The “Big O” notation classifies algorithms into classes such as n, n^2, log(n), n*log(n), etc. These classifications indicate that their algorithms will have to execute, for example, log(n) calculations to produce a result for n elements. The binary search algorithm is an excellent example of such a log(n) algorithm.
In our case, however, there is not much to calculate. We have already established that the number of permutations for n elements is n!. Even the best algorithm in the universe can’t solve it without executing at least n! calculations, so we can’t do any better. But we can do a bit worse. First, we’ll write the most straightforward algorithm possible, with much higher complexity (n^n) and lower performance.
Basic Permutations Algorithm
The basic algorithm is simple and can be visualized as a bicycle lock with rolling numbers. To find out all the permutations of three digits, we can choose all possible positions of all three wheels on the lock, and we will get this: 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, and 222.
In other words, there are 3^3=27 positions or three loops with three elements:
public static void PrintAllPossiblePositions()
{
int counter = 1;
for (int p0 = 0; p0 < 3; p0++)
for (int p1 = 0; p1 < 3; p1++)
for (int p2 = 0; p2 < 3; p2++)
Console.WriteLine($"Position [{counter++, 2}]: {p0}{p1}{p2}");
}
But not all results are valid. With permutations, there can’t be repeating digits. So from this set of 27 results, we must discard every result with repeating digits. By applying that, we will get the correct result: 012, 021, 102, 120, 201, and 210.
To print out only permutations, we have to discard results with repeating digits:
public static void PrintPermutations()
{
int counter = 1;
for (int p0 = 0; p0 < 3; p0++)
for (int p1 = 0; p1 < 3; p1++)
for (int p2 = 0; p2 < 3; p2++)
{
if ((p0 != p1) && (p0 != p2) && (p1 != p2))
Console.WriteLine($"Permutation [{counter++,2}]: {p0}{p1}{p2}");
}
}
This method will print the permutations of 3 elements.
So, we have written our first working algorithm for generating permutations. However, as discussed in the beginning, the algorithm is inefficient since we calculate 27 elements to produce just six results.
Algorithm Improvement
We can improve a lot with a small algorithm change.
Let’s take these arrangements: 000, 001, 002. We can discard all three arrangements in the second loop. As soon as we see another 0, we can quit, as there can’t be two zeros in a given permutation:
public static void PrintPermutationsImproved()
{
int counter = 1;
for (int p0 = 0; p0 < 3; p0++)
for (int p1 = 0; p1 < 3; p1++)
{
if (p1 == p0) continue; // Just skip the whole inner loop(!)
for (int p2 = 0; p2 < 3; p2++)
{
if ((p2 == p0) || (p2 == p1)) continue;
Console.WriteLine($"Permutation [{counter++,2}]: {p0}{p1}{p2}");
}
}
}
We avoid executing the third loop when we discover that the second position would have the same digit as the first. This algorithm is much better than the first one, but they both have one major drawback!
They are useless for generating permutations of 4 or 6 elements. To display all the permutations of 4 or 6 elements, we need a method with 4 or 6 for loops. This will require a different method for each N, making this approach less than ideal.
Recursion to Save the Day
Fortunately, many problems, especially combinatorial problems, can be solved using recursion. We have to find how a smaller N fits a bigger N. So to use recursion, we will need to find out how to generate permutations of 4 elements (or N elements) if we know how to build permutations with three elements (or N-1 elements).
We already have permutations of 3 elements: 012, 021, 102, 120, 201, and 210. If we add element 3, what do we get? Well, for starters, we should get 3012, 3021, 3102, 3120, 3201, 3210, and then more of them. So we have created new permutations by adding a new element to existing permutations, which is key to the solution!
First, we have a bag of elements. Then, we take the first element out of the bag and create all the permutations of the remaining elements in the bag. We paste the first element to every generated permutation. Next, we return the first element to the bag and take the next element out. We repeat this process until we have used all the elements in the bag.
To illustrate this idea, let’s try generating permutations for four elements using the algorithm.
The Recursive Algorithm
Let’s say we have a bag of four elements: 0, 1, 2, and 3. We take the first element out of the bag, which is 0, and create permutations of the remaining elements (1, 2, and 3). We generate six permutations: 123, 132, 213, 231, 312, and 321. To obtain the final permutations, we add 0 to the beginning of each generated permutation: 0123, 0132, 0213, 0231, 0312, and 0321. We then return 0 to the bag and take the next element out, which is 1. The bag now contains elements 0, 2, and 3; their permutations are 023, 032, 203, 230, 302, and 320. Now add 1 to the beginning of each permutation to obtain: 1023, 1032, 1203, 1230, 1302, and 1320. Repeat the same process for elements 2 and 3.
Ultimately, we have used all four elements in the bag and generated all possible permutations. The total number of permutations generated is 24 (4 * 6), which is the correct result.
The code written in C# follows the algorithm:
public static void RecursiveAlgorithm(string elementsOutOfTheBag, List<int> elementsInTheBag)
{
if (elementsInTheBag.Count == 0)
Console.WriteLine($"Permutation: {elementsOutOfTheBag}");
else
{
foreach (var element in elementsInTheBag)
{
List<int> newBag = elementsInTheBag.Where(e => e != element).ToList();
RecursiveAlgorithm(elementsOutOfTheBag + element, newBag);
}
}
}
The method accepts the string of already positioned elements and a bag of not-yet-used elements. If the bag is empty, we have reached the end and have the resulting permutation. Otherwise, we recursively execute the same algorithm with the next element.
Where to Begin
To initiate this recursive method, we require a starting position. In this case, it is an empty string and all the elements:
public static void PrintPermutationsRecursively()
{
RecursiveAlgorithm("", new List<int> { 0, 1, 2, 3, 4 });
}
The result will be 120 permutations for five elements.
However, we should note that this method does not have a limit on the number of elements. This simple and easy-to-understand method produces a working result for any quantity desired. We can generate permutations for eight elements by simply calling:
RecursiveAlgorithm("", new List<int> { 0, 1, 2, 3, 4, 6, 7, 8 });
Executing this code generates 40,320 permutations, keeping our algorithm busy for a while.
Breaking the Recursion
Although recursion is an essential technique, there is always a potential problem with it. If a long recursion isn’t allowed to exit, it can become a severe problem. Therefore, as programmers, we must be sure our algorithm provides a way out.
In our case, this is relatively easy to check because, with every recursion, we take one more element out of the bag. Eventually, we will remove all the elements, and the recursion will end.
It’s always a good idea to write tests to verify whether an algorithm provides the correct result, and you can find our tests in the GitHub project.
Recursive Performance
To determine our algorithm’s performance, we will have to measure it. We will use a standard tool: BenchmarkDotNet.
To benchmark different algorithms fairly, we have to strip everything nonessential from them. In our case, we will rewrite the algorithms so that they will not write results to the console, and they will permutate elements in the same memory location.
The second requirement regarding memory location may not be immediately apparent, but it is essential. Since there are many permutations, it makes sense to generate all permutations in the same memory location and not utilize memory unnecessarily for each new permutation.
To this end, we will also introduce a new parameter: benchmark. If this parameter is true, we will elect to “forget” each permutation. We will generate it and move to the next one. This way, measuring speed and memory consumption will be fairer.
Rewriting the Recursive Algorithm
By stripping the console output from the algorithm and collecting the results to list, we will get our next iteration of the recursive algorithm:
private void RecursiveGenerator(List<byte[]> result, byte[] input, byte fixedPosition,
List<byte> freeNumbers, bool banchmarks)
{
if (fixedPosition == input.Length)
{
if (!banchmarks) result.AddCopy(input);
}
else
{
for(int i = 0; i < freeNumbers.Count; ++i)
{
var newFreeNumbers = new List<byte>(freeNumbers);
newFreeNumbers.RemoveAt(i);
input[fixedPosition] = freeNumbers[i];
RecursiveGenerator(result, input, (byte)(fixedPosition + 1), newFreeNumbers);
}
}
}
The algorithm is exactly the same as before; only the parameters are slightly different.
The first parameter is a list that will return the resulting permutations. The second parameter is a memory location where the algorithm will generate permutations. So every permutation will occupy the same memory (the same array), and before we add it to the resulting list, we have to make a copy! The third parameter counts how many elements in the array we have already constructed, and the algorithm will stop when we generate the whole permutation. The fourth parameter is a bag of unused elements, just as before. The last parameter is a flag that tells the algorithm if we are measuring time/space, so in that case, it will not generate the resulting output.
Rewriting the Basic and Improved Basic Algorithms
In addition, we also need to rewrite the Basic and Improved Algorithms. Specifically, we will focus on the methods used to generate permutations of 3 elements. Given that the code for generating five elements using the Basic or Improved algorithm is quite lengthy, here we will only modify the code for generating permutations of 3 elements:
private List<byte[]> GetPermutations3(byte[] input, bool doBanchmarks)
{
var result = new List<byte[]>();
var number = input.Length;
for (byte i0 = 0; i0 < number; ++i0)
for (byte i1 = 0; i1 < number; ++i1)
for (byte i2 = 0; i2 < number; ++i2)
if ((i0 != i1) && (i0 != i2) &&
(i1 != i2))
{
input[0] = i0;
input[1] = i1;
input[2] = i2;
if (!doBanchmarks) result.AddCopy(input);
}
return result;
}
To do so, we create an array to store the results and include a flag to indicate if we are measuring the code’s performance. The algorithm remains largely the same, with the only changes made to improve efficiency using the same memory location.
We can apply these same changes to the Improved algorithm as well:
private List<byte[]> GetPermutations3(byte[] input, bool doBanchmarks)
{
var result = new List<byte[]>();
var number = input.Length;
for (byte i0 = 0; i0 < number; ++i0)
{
input[0] = i0;
for (byte i1 = 0; i1 < number; ++i1)
{
if (i1 == i0) continue;
input[1] = i1;
for (byte i2 = 0; i2 < number; ++i2)
{
if ((i2 == i0) || (i2 == i1)) continue;
input[2] = i2;
if (!doBanchmarks) result.AddCopy(input);
}
}
}
return result;
}
Comparing Algorithms
By making these changes, we can finally measure the algorithms’ performance. Specifically, we will test their ability to generate permutations of 2, 4, 6, and 8 elements. The results of our testing on a typical modern desktop computer are:
| Method | Items | Mean | Allocated | |------------------- |------ |-----------------|------------------| | BasicAlgorithm | 4 | 352.7 ns | 176 B | | ImprovedAlgorithm | 4 | 190.5 ns | 176 B | | RecursiveAlgorithm | 4 | 1,518.5 ns | 4336 B | | BasicAlgorithm | 6 | 92,406.8 ns | 176 B | | ImprovedAlgorithm | 6 | 8,359.9 ns | 176 B | | RecursiveAlgorithm | 6 | 45,411.8 ns | 125424 B | | BasicAlgorithm | 8 | 23,743,306.9 ns | 192 B | | ImprovedAlgorithm | 8 | 2,218,982.5 ns | 178 B | | RecursiveAlgorithm | 8 | 2,593,615.1 ns | 7014642 B |
From this table, it is evident that the Improved algorithm is the fastest. Additionally, we can see that as the number of elements to be permuted increases, the Basic algorithm’s efficiency decreases while the recursive algorithm’s efficiency improves. However, we must also consider that the recursive algorithm significantly impacts memory.
Therefore, the recursive algorithm appears not as optimal as we initially thought. While it is currently the only algorithm capable of generating permutations for any number of elements, it is not ideal. On the other hand, if we want an Improved algorithm for 12 elements, we would need to create a method with 12 for loops, which is impractical.
Raising the Bar
Can we do better? Certainly!
While the three previous algorithms were relatively easy to write, they were not the best possible solutions. More advanced and efficient algorithms have been developed, such as Heap’s Algorithm for generating permutations.
Generate Permutations With the Heap’s Algorithm
This algorithm, named after B. R. Heap, who published it in 1963, is also recursive. It involves swapping elements in a set and recursively generating permutations of the smaller set until all permutations have been generated. Fortunately, we have all the tools we need to implement Heap’s Algorithm in C#:
private void Heaps(List<byte[]> result, byte[] input, byte size, bool banchmarks)
{
if (size == 1)
{
if (!banchmarks) result.AddCopy(input);
}
else
{
for (int i = 0; i < size; i++)
{
Heaps(result, input, (byte)(size - 1));
if (size % 2 == 1)
(input[size - 1], input[0]) = (input[0], input[size - 1]);
else
(input[size - 1], input[i]) = (input[i], input[size - 1]);
}
}
}
Despite being short and having the same parameters as our previous recursive algorithm, Heap’s Algorithm is significantly faster and more memory-efficient, as it avoids the need to generate a bag during every recursion. To demonstrate this, we can measure the algorithm and obtain the results:
| Method | Items | Mean | Allocated | |------------------- |------ |-----------------|-----------| | ImprovedAlgorithm | 4 | 190.5 ns | 176 B | | HeapsAlgorithm | 4 | 149.3 ns | 176 B | | ImprovedAlgorithm | 6 | 8,359.9 ns | 176 B | | HeapsAlgorithm | 6 | 3,377.0 ns | 176 B | | ImprovedAlgorithm | 8 | 2,218,982.5 ns | 178 B | | HeapsAlgorithm | 8 | 195,455.8 ns | 176 B |
The theory behind the Heap’s algorithm is described in great detail on Wikipedia.
Conclusion
The fact that we are unlikely to find better algorithms than some of the world’s great programming minds have already discovered does not mean we should give up. We should consider the various possibilities, write different algorithms and ideas, and not always settle for “the best algorithm” available online. In truth, there is rarely a “best one” for every case, as it depends on the specific problem we have to solve and the type of data it entails.
In this case, we have demonstrated how to approach the problem of generating permutations, and once we have our starting point, we can continue to seek out and craft ever-better algorithms.
