If you have a set of things, a permutation is a specific way that you can list those things. Although algorithms exist to list every permutation, most of them rely on recursion – the calling of a function from within itself – which is horribly inefficient.
If you want a non-recursive algorithm that lists every permutation, keep reading…
Table of Contents
Permutations vs. Combinations vs. This Article
A combination is how a set of things can be grouped, ignoring sequence. So if I have the letters “A”, “B”, and “C”, and I say “give me all combinations of length 3”, the answer is 1: “ABC”.
The way that 3 out of 3 of these objects can be grouped together, regardless of their sequence is just one.
If we look at “BAC” or “CAB”, those are the same combination (grouping without order) of those letters.
However, a permutation is a grouping that takes sequence in to account. So if I say “give me all permutations that begin with ‘A'”, the answer is:
- ABC and
- ACB
Although both of these are the same combination of “A”, “B”, and “C”, they are each a unique permutation, because a permutation takes in to account the sequence in which we chose them.
I want to ignore the math of this, as there are many existing videos and articles that do an excellent job of explaining it, and anything I could offer here would be redundant.
Additionally, we won’t be discussing permutations that allow multiple selections of each element (“AAA”, “AAB”, etc…). We will assume that each element can be selected only once.
The reason you might want to have an algorithm generate every possible permutation is to examine every possible sequence of choices, such as optimizing the path through a maze, or figuring out the fewest trucks required to carry your packages.
Although, in general, this approach is horribly inefficient and slow, it’s incredibly thorough, as you end up literally checking every possibility.
There are also applications for procedural level generation and other aspects of gaming, where you can ensure that difficulty is progressive but random, or that each level is unique but contains all elements of a set (etc).
A Word on Recursion
Recursion occurs when a function calls itself.
The classic example of recursion is the n! (factorial) operation:
/* Simple Recursion Example */ #include <stdio.h> int factorial(int n) { if(n>1) { return(n*factorial(n-1)); } else { return(1); } } void main(void) { printf("Factorial of %d is %d.",4,factorial(4)); printf("Factorial of %d is %d.",10,factorial(10)); }
The output of the above, is of course:
Factorial of 4 is 24. Factorial of 10 is 3628800.
In the example above, the function calculates the factorial of a number by multiplying a number n times the result of calling itself with n-1.
An ‘if’ statement is used to make sure that when we hit 1, which is the bottom, we simply return 1 (1! = 1) rather than continue. As the level above receives the return result, it multiplies by its private value of n, so the level above 1 multiplies 2*1=2, and then returns 2. The level above multiplies 3*2 and returns 6, etc.
In general, the problem with recursion is that it’s both expensive and slow.
- For any number “n”, the variable n must be pushed on to the stack “n” times. So “n” copies of n exist in memory, which is expensive.
- A function call is always a far jump, which is slow (less relevant to modern CPUs), but also requires that every variable must be pushed on to the stack before the next function call takes over.
The same factorial function can be written with linear code:
int factorial(int n) {
int i;
int ret=1;
for(i=2;i<=n;i++) ret*=i;
return(ret);
}
The code in main is identical, but now there is only a single function call – the rest is handled within a simple ‘for’ loop.
Avoiding recursion is good practice, and most of the time, it can be replaced with conventional, linear code.
Recursive Permutation Function
Although our example of the factorial function is linear, polynomial recursive functions such as enumerating permutations don’t scale well, as they tend to take n! time and n^2 memory.
In the example below, we will use recursion to enumerate all possible permutations of the string “ABCD”.
#include <stdio.h> #include <string.h> /* -- Permutation String -- */ static char *pstring="ABCD"; /* -- Declare function used later -- */ void permutation(char *s, int p); /* -- -- MAIN -- -- */ void main(void){ printf("String: %s, %d chars\n\n",pstring,strlen(pstring)); permutation(pstring,0); } /* -- Permutation function -- */ void permutation(char *s, int p){ /* s - String that holds the current permutation /* p - Pivot point. Everything to the left of the /* pivot is fixed, and we want to enumerate all /* permutations of right-hand substring starting /* starting at p */ int pp,c; int l=strlen(s); /* Private working copy of s[] */ char ss[l+1]; ss[l]=0; /* Zero terminated */ if(p<l) { /* -- Copy static part of the string -- */ for(pp=0;pp<p;pp++) ss[pp]=s[pp]; /* -- Iterate permutations starting at p -- */ for(pp=p;pp<l;pp++) { /* Grab next char in remaining sequence of s */ ss[p]=s[pp]; /* Copy chars left and right of pp */ for(c=p+1;c<l;c++) ss[c]=(c<=pp)?s[c-1]:s[c]; /* Enumerate downstream permutations */ permutation(ss,p+1); } } else { /* If p==l then we have a complete permutation */ printf(" %s\n",s); /* This works, HOWEVER, we are strlen(pstring) /* levels deep at this point. Any work would have /* to be done inside this section of code, or we /* would have to call yet another function to do /* any heavy lifting. */ } }
Here is the output:
String: ABCD, 4 chars ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
Here is how it works:
- Each level assumes that the level above it passes a valid permutation plus a “pivot point”.
- Everything to the left of the pivot was calculated by the layers above. So the function starts by creating a private copy of fixed portion of the original string. If it were to modify the original string, then the layers above would no longer have access to a complete set.
- The function then iterates from the pivot (p) to the end of the string. At each position (pp), it grabs the corresponding char from the original string (s), and then copies the remaining chars to the left and right of pp, all to the right of p in the new string (ss).
- The final step of each iteration is to call itself with the modified, copied string (ss), and pivot position p+1.
- The next layer down then repeats the process for the remaining characters.
- When the pivot (p) reaches the string length, we have a complete permutation. In this example, we simply print out the permutation, but this would also be the point where we could pass the permutation along to other code that does some real work, such as checking to see if it’s a valid solution to a maze, or the like.
This last part gets tricky, as the permutation only exists within the private context of a function that’s nested n-layers deep. To actually do anything useful with it, your code has one of several equally-bad options:
- Put the ‘real work’ code inside the ‘if’ block of the recursive function. This makes the code much less modular, and more difficult to troubleshoot, with a monolithic slab of code stuffed in to the end of this one function.
- Put the ‘real work’ inside a chain function. This makes it a little bit more modular, but unfortunately, the permutation itself still only exists in the context of the recursive function. Although the chained function receives a copy, the main program has no knowledge of it.
- The recursive function could store off a list of all permutations, for example, in an external file, and then the main program could retrieve them. This approach means that no ‘real work’ will be completed until after the last permutation is calculated. For long strings, your program could spend weeks or days just calculating all of the permutations, which now also requires lots of external storage, before it does anything useful.
- Shell out to another program, passing the permutation as an argument.
- You could implement some kind of elaborate multi-threading scheme, but this is way more complicated than necessary.
A better approach is to use a global variable and a callback function.
Here is a revised version, where the function writes each complete permutation to a global variable called ‘perm’, and then calls a callback function.
#include <stdio.h> #include <stdlib.h> #include <string.h> /* -- Permutation String -- */ static char *pstring="ABCD"; /* -- Declare functions used later -- */ void permutation(char *s, int p, void (*call)()); void callback(void); /* -- Global Variable -- */ char *perm; /* -- -- MAIN -- -- */ void main(void){ /* Allocate memory and put zero terminator */ perm=(char *)malloc((strlen(pstring)+1)*sizeof(char)); perm[strlen(pstring)]=0; /* Main code */ printf("String: %s, %d chars\n\n",pstring,strlen(pstring)); permutation(pstring,0,callback); } void callback(void){ /* The entire point of this function is to avoid /* heavily nested code */ /* A valid permutation sits in the 'perm' global variable */ printf("Print from callback: %s\n",perm); /* Do some real work */ /* Unfortunately, we still have strlen(pstring) /* copies of pstring on the stack, and each permutation /* requires strlen(pstring) function calls */ } /* -- Modified Permutation function -- */ void permutation(char *s, int p, void (*call)()){ int pp,c; int l=strlen(s); /* -- we still have to create a private copy -- */ char ss[l+1]; /* Private working copy of s[] */ ss[l]=0; /* Zero-terminated */ if(p<l) { /* -- Copy static part of the string -- */ for(pp=0;pp<p;pp++) ss[pp]=s[pp]; /* -- Iterate permutations starting at p -- */ for(pp=p;pp<l;pp++) { /* Grab next char in remaining sequence of s */ ss[p]=s[pp]; /* Copy chars left and right of pp */ for(c=p+1;c<l;c++) ss[c]=(c<=pp)?s[c-1]:s[c]; /* Enumerate downstream permutations */ permutation(ss,p+1,call); } } else { /* If p==l then we have a complete permutation */ /* Copy to global var - zero termination is already at the end */ for(pp=0;pp<l;pp++) perm[pp]=s[pp]; /* printf(" %s\n",perm); */ /* Instead of doing work from inside the recursive function, /* use callback pointer function instead */ call(); } }
Although this is largely identical to the first version, rather than doing the work inside the function itself, we have a “work” function called ‘callback’. When we call the permutation function from main, we pass a pointer to the callback function (‘call’ within the scope of the function). In addition, rather than using a private copy of the permutation, it stores each valid permutation in the global variable ‘perm’.
This makes the code a lot more modular and easier to troubleshoot, but still requires the overhead of recursion.
Non-Recursive Approach
Wouldn’t it be nice if we could enumerate permutations WITHOUT recursion?
So, how do we do that?
The first thought that comes to mind is to use an array as a big counter. Similar to one of those mechanical tally counters, where each click advances the 1’s place. When the 1’s place rolls to 0, it advances the 10’s place.
This continues until the 10,000’th click rolls the entire system back to 0000.
We could easily do the same thing with an array:
int len=4;
char counter[len]={0};
int click(void){
int p=len-1;
while(p>=0) {
counter[p]++;
if(counter[p]>=len) {
counter[p]=0;
p--;
} else {
p=-2;
}
}
return(p+1);
}
Each digit will count from 0 to len-1. In this case, len=4, so each digit will count from 0..3. If the lowest digit rolls, it sets that digit back to zero, and decrements p. The loop then increments the next digit, and this continues until we end up with a valid counter digit, or we run out of digits to roll. The function then returns -1 if successful (we use the flag value of -2+1 = -1) or 0 if we ran out of digits (p=-1+1 = 0).
After each click, we can use the counter value to generate a permutation from the original string:
char *pstring="ABCD";
char *perm;
void main(void){
int i;
perm=(char *)malloc((len+1)*sizeof(char));
perm[len]=0; /* Don't forget the zero string terminator */
do {
/* for(i=0;i<len;i++) perm[i]=pstring[i]; */
/* edited on 8/30/2020 - forgot to use the counter -- oops */
for(i=0;i<len;i++) perm[i]=pstring[counter[i]];
printf("%s",perm);
} while(click());
}
This will start the counter at all zeros, and then loop until the counter “resets” to all zeros. At each counter position, it builds a string from the original by using the value of each counter digit as an index.
Unfortunately, not every counter value is a valid permutation. 0000 = “AAAA”, 0001 = “AAAB”, etc…
Although there are only 4*3*2*1 = 24 valid permutations, the ‘click’ function will produce every possible permutation, or 4*4*4*4 = 256. If we were to use this method, we would have to check each permutation to see if it’s valid – is there only one “A”, only one “B”, etc…
What’s nice about the recursive function, even though it’s inefficient, is that it uses the pivot to determine what needs to be done – it assumes everything to the left of the pivot is “safe” and only operates at the pivot and beyond. It selects one position at each iteration to be the new pivot value, and then kicks the rest down the road in to the next recursion.
If we could do the same thing with our counter – guarantee that everything to the left of a given position is unique, then all we would have to do is operate on what’s left.
Looking at our string “ABCD”, here are the first few permutations:
ABCD ABDC ACBD ACDB ADBC ADCB
The next set of permutations begins with “B”:
BACD BADC BCAD BCDA BDAC BDCA
The first position has 4 possibilities, so we could simply iterate over each position from the original string: A, then B, then C, then D.
The second position only has 3 possibilities based on whatever value has been selected by the first position.
From a code perspective, this still doesn’t help us, as we would have to check each counter digit to see whether any other counter digit held its value, which is computationally expensive.
If we look at the right-most two letters, they swap at every even permutation. In the first line, “CD” becomes “DC” in the second line. The reason this happens is that when we make the second-to-last selection, only one option remains. So there are only ever two possibilities left, and if we know one of them, we can simply swap the last two symbols in order to obtain the other.
If we look at just 3 positions, we see this pattern:
xBC
xCB (swapped 2 and 3)
BxC (swapped 1 and 2 from the original string)
BCx (swapped 2 and 3 again)
CxB (This is where things kind of go left)
CBx (swapped 2 and 3 again)
I played with various ways to take the 4th string “BCx” to get the final set of permutations beginning with “CxB”, but nothing works reliably, especially when you go to 4, 5, 6 positions and beyond.
However, if we modify the sequence slightly, we get this:
xBC xCB (swapped 2,3 from the original string) BxC (swapped 1,2 from the original string) BCx (swapped 1,2 then 2,3 from original) CBx (swapped 1,3 from original) CxB (swapped 1,3 then 2,3 from original)
You might not see the hidden pattern, but we could re-write the entire sequence in terms of taking the original string, and then performing swaps on the first and second symbols:
xBC (Original string) xBC (swap 1,1 and 2,2) xCB (swap 1,1 and 2,3) BxC (swap 1,2 and 2,2) BCx (swap 1,2 and 2,3) CBx (swap 1,3 and 2,2) CxB (swap 1,3 and 2,3)
For each swap, if we subtract the starting from the ending position, we get something that resembles a counter:
xBC (Original) xBC 1-1 = 0 ; 2-2 = 0 ; [00] xCB 1-1 = 0 ; 3-2 = 1 ; [01] BxC 2-1 = 1 ; 2-2 = 0 ; [10] BCx 2-1 = 1 ; 3-2 = 1 ; [11] CBx 3-1 = 2 ; 2-2 = 0 ; [20] CxB 3-1 = 2 ; 3-2 = 1 ; [21]
We can interpret each digit (d) of the counter, starting at the left-most position, of how to take the original string and swap the current position (p) with d positions to the right (d+p).
For example, in the last two lines, we swap “x” in position 1 with “C” in position 3 – two positions to the right. We then go on to the next digit, which is either 0, (no swap: “Bx”) or 1, which indicates that middle position should swap with the right: “xB”.
Notice that the 10’s digit has 3 possibilities: 0, 1, and 2. The 1’s digit only has two: 0 or 1. This is because we reduce the number of remaining positions at each selection. If we were to add one more letter, then the first position would have 4 possibilities: 0, 1, 2, or 3:
ABCD (Always start with the Original string) ABCD [000] (no swaps) ABDC [001] (swap 3 and (3+1)=4) ACBD [010] (swap 2 and (2+1)=3) ACDB [011] (swap 2 and (2+1)=3, and then 3 and (3+1)=4) ADCB [020] (swap 2 and (2+2)=4) ADBC [021] (swap 2 and (2+2)=4, and then 3 and (3+1)=4) BACD [100] (swap 1 and 1+1=2) BADC [101] (swap 1 and 1+1=2; 3 and 3+1=4) BCAD [110] (swap 1 and 1+1=2; 2 and 2+1=3) BCDA [111] (swap 1 and 1+1=2; 2 and 2+1=3; 3 and 3+1=4) BDCA [120] (swap 1 and 1+1=2; 2 and 2+2=4) BDAC [121] (swap 1 and 1+1=2; 2 and 2+2=4; 3 and 3+1=4) CBAD [200] (swap 1 and 1+2=3) CBDA [201] (swap 1 and 1+2=3; 3 and 3+1=4) CABD [210] (swap 1 and 1+2=3; 2 and 2+1=3) CADB [211] (swap 1 and 1+2=3; 2 and 2+1=3; 3 and 3+1=4) CDAB [220] (swap 1 and 1+2=3; 2 and 2+2=4) CDBA [221] (swap 1 and 1+2=3; 2 and 2+2=4; 3 and 3+1=4) DBCA [300] (swap 1 and 1+3=4) DBAC [301] (swap 1 and 1+3=4; 3 and 3+1=4) DCBA [310] (swap 1 and 1+3=4; 2 and 2+1=3) DCAB [311] (swap 1 and 1+3=4; 2 and 2+1=3; 3 and 3+1=4) DACB [320] (swap 1 and 1+3=4; 2 and 2+2=4) DABC [321] (swap 1 and 1+3=4; 2 and 2+2=4; 3 and 3+1=4)
If you add one, the entire counter rolls to 000, so we have enumerated every permutation.
- We always swap to the right, assuming that any work performed on the left side of the string is complete
- The maximum counter value for each position, given length (l) and position (p) is l-p. So in the 3rd position, 4-3=1, so position 3 can be 0 or 1.
- In the 4th position, len 4 – position 4 = 0, which is why we don’t need a 4th digit.
We can take our counter code from above and modify it slightly:
int click(void){
int p=len-1;
while(p>=0) {
counter[p]++;
if(counter[p]>=(len-p)) {
counter[p]=0;
p--;
} else {
p=-2;
}
}
return(p+1);
}
To build a permutation from our counter, we start with the original string, and then perform the swaps:
int len=4;
char *pstring="ABCD"
char perm[len+1];
int counter[len]={0};
int click(void);
void buildperm(void) {
int i;
char c;
/* Populate the string from original */
for(i=0;i<len;i++) perm[i]=pstring[i];
for(i=0;i<len;i++) if(counter[i]>0) {
c =perm[i];
perm[i] =perm[i+counter[i]];
perm[i+counter[i]]=c;
}
}
If counter[i]=0, then it would swap with itself – counter[i+0]. For counter[i]>0, counter becomes the offset to the right – i+counter[i].
Now, from our main program, we can call ‘click’ to increment the counter, and ‘buildperm’ to build a valid permutation from a given counter value.
Putting it All Together
Here is the final version:
#include <stdio.h> #include <stdlib.h> #include <string.h> /* -- Permutation String -- */ static char *pstring="ABCD"; /* -- Declare functions used later -- */ void perminit(char *s); /* Initialize the poly counter array */ int permtick(void); /* Advance to the next permutation */ void buildperm(char *s); /* Build current permutation from poly */ /* -- Global Variables -- */ char *perm, *poly; int plen; /* -- -- MAIN -- -- */ void main(void){ /* Main code */ printf("String: %s, %d chars\n\n",pstring,strlen(pstring)); /* Initialize the poly counter */ perminit(pstring); do { /* Build current permutation from poly */ buildperm(pstring); printf("Print from main loop: %s\n",perm); /* Do some real work */ /* The stack is lightweight because the entire /* state is held in poly, and there is no need /* for the function callback nonsense */ /* Permtick advances poly to the next permutation /* and returns 0 when there are none left */ } while(permtick()); } void perminit(char *s) { /* We have moved the init code to an init function, /* where it truly belongs */ plen=strlen(s); perm=(char *)malloc((plen+1)*sizeof(char)); perm[plen]=0; poly=(char *)malloc((plen+1)*sizeof(char)); /* poly is a byte array that we are going to use as a big counter */ int p; for(p=0;p<plen;p++) poly[p]=0; } int permtick(void) { /* Each time we call permtick, it increments our poly counter */ int ret=-1; /* Return True by default */ int p=plen-2; /* Start at 2nd to last position */ while( p >= 0 ) { /* Increment poly digit */ poly[p]++; /* If poly digit exceeds plen-p, move to /* the next digit and loop */ if(poly[p]>=(plen-p)) { poly[p]=0; p--; /* FYI - this is why poly[plen-1] is always 0: /* That's it's maximum value, which is why we /* start at plen-2 */ } else { p=-2; /* Done looping */ } } /* All permutations have been calculated and p=-1 */ if(p==-1) ret=0; return(ret); } void buildperm(char *s) { /* Build a permutation from the poly counter */ char c; int i; /* Start with a fresh copy of the string */ for(i=0;i<plen;i++) perm[i]=s[i]; /* Swap digits based on each poly digit */ /* if poly[i]>0 then swap with the (i+nth) digit */ for(i=0;i<(plen-1);i++) if(poly[i]>0) { c =perm[i]; perm[i] =perm[i+poly[i]]; perm[i+poly[i]]=c; } }
Now, we have fairly modular code without the need for recursion nor callbacks, that we could use for almost anything.
By changing the data types of poly and perm, and with a few code changes, you could enumerate much larger sets, and not necessarily strings. perm[i] simply becomes an index in to an array of things: thing[perm[i]]
For example:
int *pstring={1, 2, 3}
int *perm, plen
char *thing={"Apple", "Banana", "Orange"}
...
buildperm(pstring)
for(i=0;i<plen;i++) printf("%s ",thing[perm[i]]);
...
All of the other logic remains the same.
Conclusion
Always avoid recursion. It’s slow and expensive.
Here, we’ve reviewed a way to enumerate permutations while keeping your code agile and flexible.
If you made it this far, thanks for hanging in there! I hope this helps you out!