{"id":6056,"date":"2020-08-29T15:23:52","date_gmt":"2020-08-29T20:23:52","guid":{"rendered":"https:\/\/justinparrtech.com\/JustinParr-Tech\/?p=6056"},"modified":"2020-08-30T10:02:59","modified_gmt":"2020-08-30T15:02:59","slug":"non-recursive-algorithm-for-enumerating-permutations","status":"publish","type":"post","link":"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/","title":{"rendered":"NON-RECURSIVE Algorithm for Enumerating Permutations"},"content":{"rendered":"<p>If you have a set of\u00a0<em>things<\/em>, a <strong>permutation<\/strong> is a specific way that you can list those things.\u00a0 Although algorithms exist to list every permutation, most of them rely on recursion &#8211; the calling of a function from within itself &#8211; which is horribly inefficient.<\/p>\n<p>If you want a <strong>non<\/strong>-recursive algorithm that lists every permutation, keep reading&#8230;<\/p>\n<p><!--more--><\/p>\n<p>&nbsp;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_81 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\"><p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<\/div><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#permutations-vs-combinations-vs-this-article\" >Permutations vs. Combinations vs. This Article<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#a-word-on-recursion\" >A Word on Recursion<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#recursive-permutation-function\" >Recursive Permutation Function<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#non-recursive-approach\" >Non-Recursive Approach<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#putting-it-all-together\" >Putting it All Together<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/non-recursive-algorithm-for-enumerating-permutations\/#conclusion\" >Conclusion<\/a><\/li><\/ul><\/nav><\/div>\n\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"permutations-vs-combinations-vs-this-article\"><\/span>Permutations vs. Combinations vs. This Article<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A\u00a0<strong>combination<\/strong> is how a set of things can be grouped, ignoring sequence.\u00a0 So if I have the letters &#8220;A&#8221;, &#8220;B&#8221;, and &#8220;C&#8221;, and I say &#8220;give me all combinations of length 3&#8221;, the answer is 1:\u00a0 &#8220;ABC&#8221;.<\/p>\n<p>The way that 3 out of 3 of these objects can be grouped together, regardless of their sequence is just one.<\/p>\n<p>If we look at &#8220;BAC&#8221; or &#8220;CAB&#8221;, those are the same combination (grouping without order) of those letters.<\/p>\n<p>However, a\u00a0<strong>permutation<\/strong> is a grouping that takes sequence in to account.\u00a0 So if I say &#8220;give me all permutations that begin with &#8216;A'&#8221;, the answer is:<\/p>\n<ul>\n<li>ABC and<\/li>\n<li>ACB<\/li>\n<\/ul>\n<p>Although both of these are the same\u00a0<strong>combination<\/strong> of &#8220;A&#8221;, &#8220;B&#8221;, and &#8220;C&#8221;, they are each a unique <strong>permutation<\/strong>, because a permutation takes in to account the sequence in which we chose them.<\/p>\n<p>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.<\/p>\n<p>Additionally, we won&#8217;t be discussing permutations that allow multiple selections of\u00a0 each element (&#8220;AAA&#8221;, &#8220;AAB&#8221;, etc&#8230;).\u00a0 We will assume that each element can be selected only once.<\/p>\n<p>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.<\/p>\n<p>Although, in general, this approach is horribly inefficient and slow, it&#8217;s incredibly thorough, as you end up literally checking every possibility.<\/p>\n<p>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).<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"a-word-on-recursion\"><\/span>A Word on Recursion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Recursion occurs when a function calls itself.<\/p>\n<p>The classic example of recursion is the n! (factorial) operation:<\/p>\n<pre><span style=\"color: #00ffff;\">\/* Simple Recursion Example *\/<\/span>\r\n\r\n#include &lt;stdio.h&gt;\r\n\r\nint factorial(int n) {\r\n    if(n&gt;1) {\r\n        <span style=\"color: #00ff00;\">return(n*factorial(n-1));<\/span>\r\n    } else {\r\n        <span style=\"color: #ffcc00;\">return(1);<\/span>\r\n    }\r\n}\r\n\r\nvoid main(void) {\r\n    printf(\"Factorial of %d is %d.\",4,factorial(4));\r\n    printf(\"Factorial of %d is %d.\",10,factorial(10));\r\n}\r\n<\/pre>\n<p>The output of the above, is of course:<\/p>\n<pre>Factorial of 4 is 24.\r\n\r\nFactorial of 10 is 3628800.<\/pre>\n<p>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.<\/p>\n<p>An &#8216;if&#8217; statement is used to make sure that when we hit 1, which is the bottom, we simply return 1 (1! = 1) rather than continue.\u00a0 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.\u00a0 The level above multiplies 3*2 and returns 6, etc.<\/p>\n<p>In general, the problem with recursion is that it&#8217;s both expensive and slow.<\/p>\n<ul>\n<li>For any number &#8220;n&#8221;, the variable n must be pushed on to the stack &#8220;n&#8221; times.\u00a0 So &#8220;n&#8221; copies of n exist in memory, which is expensive.<\/li>\n<li>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.<\/li>\n<\/ul>\n<p>The same factorial function can be written with linear code:<\/p>\n<pre>int factorial(int n) {\r\n    int i;\r\n    int ret=1;\r\n\r\n    <span style=\"color: #00ff00;\">for(i=2;i&lt;=n;i++) ret*=i;<\/span>\r\n\r\n    return(ret);\r\n}<\/pre>\n<p>The code in main is identical, but now there is only a single function call &#8211; the rest is handled within a simple &#8216;for&#8217; loop.<\/p>\n<p>Avoiding recursion is good practice, and most of the time, it can be replaced with conventional, linear code.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"recursive-permutation-function\"><\/span>Recursive Permutation Function<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Although our example of the factorial function is linear, polynomial recursive functions such as enumerating permutations don&#8217;t scale well, as they tend to take n! time and n^2 memory.<\/p>\n<p>In the example below, we will use recursion to enumerate all possible permutations of the string &#8220;ABCD&#8221;.<\/p>\n<pre>#include &lt;stdio.h&gt;\r\n#include &lt;string.h&gt;\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Permutation String -- *\/<\/span>\r\nstatic char *pstring=\"ABCD\";\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Declare function used later -- *\/<\/span>\r\nvoid permutation(char *s, int p);\r\n\r\n<span style=\"color: #00ffff;\">\/* -- -- MAIN -- -- *\/<\/span>\r\nvoid main(void){ \r\n    printf(\"String: %s, %d chars\\n\\n\",pstring,strlen(pstring));\r\n    permutation(pstring,0);\r\n}\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Permutation function -- *\/<\/span>\r\nvoid permutation(char *s, int p){\r\n    <span style=\"color: #00ffff;\">\/* s - String that holds the current permutation\r\n<\/span>    <span style=\"color: #00ffff;\">\/* p - Pivot point.  Everything to the left of the \r\n    \/*     pivot is fixed, and we want to enumerate all \r\n    \/*     permutations of right-hand substring starting\r\n    \/*     starting at p   *\/<\/span>\r\n    int pp,c;\r\n    int l=strlen(s);\r\n\r\n    <span style=\"color: #00ffff;\">\/* Private working copy of s[] *\/<\/span>\r\n    <span style=\"color: #ffcc00;\">char ss[l+1];<\/span>\r\n    ss[l]=0;  <span style=\"color: #00ffff;\">\/* Zero terminated *\/<\/span>\r\n\r\n    if(p&lt;l) {\t\r\n        <span style=\"color: #00ffff;\">\/* -- Copy static part of the string -- *\/<\/span>\r\n        for(pp=0;pp&lt;p;pp++) ss[pp]=s[pp];\r\n\r\n        <span style=\"color: #00ffff;\">\/* -- Iterate permutations starting at p -- *\/<\/span>\r\n        for(pp=p;pp&lt;l;pp++) {\r\n\r\n            <span style=\"color: #00ffff;\">\/* Grab next char in remaining sequence of s *\/<\/span>\r\n            ss[p]=s[pp];\r\n\r\n            <span style=\"color: #00ffff;\">\/* Copy chars left and right of pp *\/<\/span>\r\n            for(c=p+1;c&lt;l;c++) ss[c]=(c&lt;=pp)?s[c-1]:s[c];\r\n\r\n            <span style=\"color: #00ffff;\">\/* Enumerate downstream permutations *\/<\/span>\r\n            <span style=\"color: #00ff00;\">permutation(ss,p+1);<\/span>\r\n\t}\r\n\r\n    } else {\r\n        <span style=\"color: #00ffff;\">\/* If p==l then we have a complete permutation *\/<\/span>\r\n        <span style=\"color: #00ff00;\">printf(\" %s\\n\",s);<\/span>\r\n\r\n        <span style=\"color: #00ffff;\">\/* This works, HOWEVER, we are strlen(pstring) \r\n        \/* levels deep at this point.  Any work would have\r\n        \/* to be done inside this section of code, or we\r\n        \/* would have to call yet another function to do\r\n        \/* any heavy lifting.  *\/<\/span>\r\n    }\r\n}\r\n<\/pre>\n<p>Here is the output:<\/p>\n<pre>String: ABCD, 4 chars\r\n\r\n ABCD\r\n ABDC\r\n ACBD\r\n ACDB\r\n ADBC\r\n ADCB\r\n BACD\r\n BADC\r\n BCAD\r\n BCDA\r\n BDAC\r\n BDCA\r\n CABD\r\n CADB\r\n CBAD\r\n CBDA\r\n CDAB\r\n CDBA\r\n DABC\r\n DACB\r\n DBAC\r\n DBCA\r\n DCAB\r\n DCBA<\/pre>\n<p>Here is how it works:<\/p>\n<ul>\n<li>Each level assumes that the level above it passes a valid permutation plus a &#8220;pivot point&#8221;.<\/li>\n<li>Everything to the left of the pivot was calculated by the layers above.\u00a0 So the function starts by creating a private copy of fixed portion of the original string.\u00a0 If it were to modify the original string, then the layers above would no longer have access to a complete set.<\/li>\n<li>The function then iterates from the pivot (p) to the end of the string.\u00a0 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).<\/li>\n<li>The final step of each iteration is to call itself with the modified, copied string (ss), and pivot position p+1.<\/li>\n<li>The next layer down then repeats the process for the remaining characters.<\/li>\n<li>When the pivot (p) reaches the string length, we have a complete permutation.\u00a0 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&#8217;s a valid solution to a maze, or the like.<\/li>\n<\/ul>\n<p>This last part gets tricky, as the permutation only exists within the private context of a function that&#8217;s nested n-layers deep.\u00a0 To actually do anything useful with it, your code has one of several equally-bad options:<\/p>\n<ul>\n<li>Put the &#8216;real work&#8217; code inside the &#8216;if&#8217; block of the recursive function.\u00a0 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.<\/li>\n<li>Put the &#8216;real work&#8217; inside a chain function.\u00a0 This makes it a little bit more modular, but unfortunately, the permutation itself still only exists in the context of the recursive function.\u00a0 Although the chained function receives a copy, the main program has no knowledge of it.<\/li>\n<li>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.\u00a0 This approach means that no &#8216;real work&#8217; will be completed until after the last permutation is calculated.\u00a0 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.<\/li>\n<li>Shell out to another program, passing the permutation as an argument.<\/li>\n<li>You could implement some kind of elaborate multi-threading scheme, but this is way more complicated than necessary.<\/li>\n<\/ul>\n<p>A better approach is to use a global variable and a callback function.<\/p>\n<p>Here is a revised version, where the function writes each complete permutation to a global variable called &#8216;perm&#8217;, and then calls a callback function.<\/p>\n<pre>#include &lt;stdio.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n#include &lt;string.h&gt;\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Permutation String -- *\/<\/span>\r\nstatic char *pstring=\"ABCD\";\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Declare functions used later -- *\/<\/span>\r\nvoid permutation(char *s, int p, void (*call)());\r\nvoid callback(void);\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Global Variable -- *\/<\/span>\r\nchar *perm;\r\n\r\n<span style=\"color: #00ffff;\">\/* -- -- MAIN -- -- *\/<\/span>\r\nvoid main(void){ \r\n    <span style=\"color: #00ffff;\">\/* Allocate memory and put zero terminator *\/<\/span>\r\n    perm=(char *)malloc((strlen(pstring)+1)*sizeof(char));\r\n    perm[strlen(pstring)]=0;\r\n\r\n    <span style=\"color: #00ffff;\">\/* Main code *\/<\/span>\r\n    printf(\"String: %s, %d chars\\n\\n\",pstring,strlen(pstring));\r\n    permutation(pstring,0,<span style=\"color: #ff00ff;\">callback<\/span>);\r\n\r\n}\r\n\r\nvoid <span style=\"color: #ff00ff;\">callback<\/span>(void){\r\n    <span style=\"color: #00ffff;\">\/* The entire point of this function is to avoid\r\n    \/* heavily nested code *\/\r\n\r\n    \/* A valid permutation sits in the 'perm' global variable *\/<\/span>\r\n    <span style=\"color: #00ff00;\">printf(\"Print from callback: %s\\n\",perm);<\/span>\r\n\r\n    <span style=\"color: #00ffff;\">\/* Do some real work *\/\r\n\r\n    \/* Unfortunately, we still have strlen(pstring) \r\n    \/* copies of pstring on the stack, and each permutation\r\n    \/* requires strlen(pstring) function calls  *\/<\/span>\r\n}\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Modified Permutation function -- *\/<\/span>\r\nvoid permutation(char *s, int p, <span style=\"color: #ff00ff;\">void (*call)()<\/span>){\r\n    int pp,c;\r\n    int l=strlen(s);\r\n\r\n    <span style=\"color: #00ffff;\">\/* -- we still have to create a private copy -- *\/<\/span>\r\n    <span style=\"color: #ffcc00;\">char ss[l+1];<\/span>   <span style=\"color: #00ffff;\">\/* Private working copy of s[] *\/<\/span>\r\n    ss[l]=0;        <span style=\"color: #00ffff;\">\/* Zero-terminated *\/<\/span>\r\n\r\n    if(p&lt;l) {    \r\n        <span style=\"color: #00ffff;\">\/* -- Copy static part of the string -- *\/<\/span>\r\n        for(pp=0;pp&lt;p;pp++) ss[pp]=s[pp];\r\n\r\n        <span style=\"color: #00ffff;\">\/* -- Iterate permutations starting at p -- *\/<\/span>\r\n        for(pp=p;pp&lt;l;pp++) {\r\n            <span style=\"color: #00ffff;\">\/* Grab next char in remaining sequence of s *\/<\/span>\r\n            ss[p]=s[pp];\r\n\r\n            <span style=\"color: #00ffff;\">\/* Copy chars left and right of pp *\/<\/span>\r\n            for(c=p+1;c&lt;l;c++) ss[c]=(c&lt;=pp)?s[c-1]:s[c];\r\n\r\n            <span style=\"color: #00ffff;\">\/* Enumerate downstream permutations *\/<\/span>\r\n            <span style=\"color: #00ff00;\">permutation(ss,p+1,call);<\/span>\r\n        }\r\n\r\n    } else {\r\n        <span style=\"color: #00ffff;\">\/* If p==l then we have a complete permutation *\/<\/span>\r\n\r\n        <span style=\"color: #00ffff;\">\/* Copy to global var - zero termination is already at the end *\/<\/span>\r\n        for(pp=0;pp&lt;l;pp++) perm[pp]=s[pp];\r\n\r\n        <span style=\"color: #ffcc00;\">\/* printf(\" %s\\n\",perm);    *\/<\/span>\r\n\r\n        <span style=\"color: #00ffff;\">\/* Instead of doing work from inside the recursive function,\r\n        \/* use callback pointer function instead                     *\/<\/span>\r\n        <span style=\"color: #ff00ff;\">call();<\/span>\r\n    }\r\n}\r\n<\/pre>\n<p>Although this is largely identical to the first version, rather than doing the work inside the function itself, we have a &#8220;work&#8221; function called &#8216;callback&#8217;.\u00a0 When we call the permutation function from main, we pass a pointer to the callback function (&#8216;call&#8217; within the scope of the function).\u00a0 In addition, rather than using a private copy of the permutation, it stores each valid permutation in the global variable &#8216;perm&#8217;.<\/p>\n<p>This makes the code a lot more modular and easier to troubleshoot, but still requires the overhead of recursion.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"non-recursive-approach\"><\/span>Non-Recursive Approach<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Wouldn&#8217;t it be nice if we could enumerate permutations WITHOUT recursion?<\/p>\n<p>So, how do we do that?<\/p>\n<p>The first thought that comes to mind is to use an array as a big counter.\u00a0 Similar to one of those mechanical tally counters, where each click advances the 1&#8217;s place.\u00a0 When the 1&#8217;s place rolls to 0, it advances the 10&#8217;s place.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-6077\" src=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/TallyCounter.png\" alt=\"\" width=\"300\" height=\"419\" srcset=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/TallyCounter.png 300w, https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/TallyCounter-215x300.png 215w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/p>\n<p>This continues until the 10,000&#8217;th click rolls the entire system back to 0000.<\/p>\n<p>We could easily do the same thing with an array:<\/p>\n<pre>int len=4;\r\nchar counter[len]={0};\r\n\r\nint click(void){\r\n    int p=len-1;\r\n\r\n    while(p&gt;=0) {\r\n        <span style=\"color: #00ff00;\">counter[p]++;<\/span>\r\n        if(counter[p]&gt;=len) {\r\n            counter[p]=0;\r\n            <span style=\"color: #00ff00;\">p--;<\/span>\r\n        } else {\r\n            p=-2;\r\n        }\r\n    }\r\n\r\n    return(p+1);\r\n}<\/pre>\n<p>Each digit will count from 0 to len-1.\u00a0 In this case, len=4, so each digit will count from 0..3.\u00a0 If the lowest digit rolls, it sets that digit back to zero, and decrements p.\u00a0 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.\u00a0 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).<\/p>\n<p>After each click, we can use the counter value to generate a permutation from the original string:<\/p>\n<pre>char *pstring=\"ABCD\";\r\nchar *perm;\r\n\r\nvoid main(void){\r\n    int i;\r\n\r\n    perm=(char *)malloc((len+1)*sizeof(char)); \r\n    perm[len]=0;  \/* Don't forget the zero string terminator *\/\r\n\r\n    do {\r\n<span style=\"color: #00ff00;\">        \/* for(i=0;i&lt;len;i++) perm[i]=pstring[i];  *\/\r\n<\/span>        <span style=\"color: #00ffff;\">\/* edited on 8\/30\/2020 - forgot to use the counter -- oops  *\/<\/span>\r\n<span style=\"color: #00ff00;\">        for(i=0;i&lt;len;i++) perm[i]=pstring[counter[i]];<\/span>\r\n        printf(\"%s\",perm);\r\n    } <span style=\"color: #ffcc00;\">while(click()<\/span>); \r\n}<\/pre>\n<p>This will start the counter at all zeros, and then loop until the counter &#8220;resets&#8221; to all zeros.\u00a0 At each counter position, it builds a string from the original by using the value of each counter digit as an index.<\/p>\n<p><strong>Unfortunately, not every counter value is a valid permutation.<\/strong>\u00a0 0000 = &#8220;AAAA&#8221;, 0001 = &#8220;AAAB&#8221;, etc&#8230;<\/p>\n<p>Although there are only 4*3*2*1 = 24 valid permutations, the &#8216;click&#8217; function will produce every possible permutation, or 4*4*4*4 = 256.\u00a0 If we were to use this method, we would have to check each permutation to see if it&#8217;s valid &#8211; is there only one &#8220;A&#8221;, only one &#8220;B&#8221;, etc&#8230;<\/p>\n<p>What&#8217;s nice about the recursive function, even though it&#8217;s inefficient, is that it uses the pivot to determine what needs to be done &#8211; it assumes everything to the left of the pivot is &#8220;safe&#8221; and only operates at the pivot and beyond.\u00a0 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.<\/p>\n<p>If we could do the same thing with our counter &#8211; guarantee that everything to the left of a given position is unique, then all we would have to do is operate on what&#8217;s left.<\/p>\n<p>Looking at our string &#8220;ABCD&#8221;, here are the first few permutations:<\/p>\n<pre>ABCD\r\nABDC\r\nACBD\r\nACDB\r\nADBC\r\nADCB<\/pre>\n<p>The next set of permutations begins with &#8220;B&#8221;:<\/p>\n<pre>BACD\r\nBADC\r\nBCAD\r\nBCDA\r\nBDAC\r\nBDCA<\/pre>\n<p>The first position has 4 possibilities, so we could simply iterate over each position from the original string:\u00a0 A, then B, then C, then D.<\/p>\n<p>The second position only has 3 possibilities based on whatever value has been selected by the first position.<\/p>\n<p>From a code perspective, this still doesn&#8217;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.<\/p>\n<p>If we look at the right-most two letters, they swap at every even permutation.\u00a0 In the first line, &#8220;CD&#8221; becomes &#8220;DC&#8221; in the second line.\u00a0 The reason this happens is that when we make the second-to-last selection, only one option remains.\u00a0 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.<\/p>\n<p>If we look at just 3 positions, we see this pattern:<\/p>\n<pre>xBC\r\nxCB  (swapped 2 and 3)\r\nBxC  (swapped 1 and 2 from the original string)\r\nBCx  (swapped 2 and 3 again)\r\n<span style=\"color: #ffcc00;\">CxB  (This is where things kind of go left)<\/span>\r\nCBx  (swapped 2 and 3 again)<\/pre>\n<p>I played with various ways to take the 4th string &#8220;BCx&#8221; to get the final set of permutations beginning with &#8220;CxB&#8221;, but nothing works reliably, especially when you go to 4, 5, 6 positions and beyond.<\/p>\n<p>However, if we modify the sequence slightly, we get this:<\/p>\n<pre>xBC\r\nxCB  (swapped 2,3 from the original string)\r\nBxC  (swapped 1,2 from the original string)\r\nBCx  (swapped 1,2 then 2,3 from original)\r\nCBx  (swapped 1,3 from original)\r\nCxB  (swapped 1,3 then 2,3 from original)<\/pre>\n<p>You might not see the hidden pattern, but we could re-write the entire sequence in terms of <strong>taking the original string<\/strong>, and then performing swaps on the first and second symbols:<\/p>\n<pre>xBC  (Original string)\r\n\r\nxBC  (swap 1,1 and 2,2)\r\nxCB  (swap 1,1 and 2,3)\r\nBxC  (swap 1,2 and 2,2)\r\nBCx  (swap 1,2 and 2,3)\r\nCBx  (swap 1,3 and 2,2)\r\nCxB  (swap 1,3 and 2,3)<\/pre>\n<p>For each swap, if we subtract the starting from the ending position, we get something that resembles a counter:<\/p>\n<pre>xBC  (Original)\r\n\r\nxBC  1-1 = 0 ; 2-2 = 0 ; [00]\r\nxCB  1-1 = 0 ; 3-2 = 1 ; [01]\r\nBxC  2-1 = 1 ; 2-2 = 0 ; [10]\r\nBCx  2-1 = 1 ; 3-2 = 1 ; [11]\r\nCBx  3-1 = 2 ; 2-2 = 0 ; [20]\r\nCxB  3-1 = 2 ; 3-2 = 1 ; [21]<\/pre>\n<p>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).<\/p>\n<p>For example, in the last two lines, we swap &#8220;x&#8221; in position 1 with &#8220;C&#8221; in position 3 &#8211; two positions to the right.\u00a0 We then go on to the next digit, which is either 0, (no swap: &#8220;Bx&#8221;) or 1, which indicates that middle position should swap with the right: &#8220;xB&#8221;.<\/p>\n<p>Notice that the 10&#8217;s digit has 3 possibilities: 0, 1, and 2.\u00a0 The 1&#8217;s digit only has two: 0 or 1.\u00a0 This is because we reduce the number of remaining positions at each selection.\u00a0 If we were to add one more letter, then the first position would have 4 possibilities:\u00a0 0, 1, 2, or 3:<\/p>\n<pre>ABCD\u00a0 (Always start with the Original string)\r\n\r\nABCD [000] (no swaps)\r\nABDC [001] (swap 3 and (3+1)=4)\r\nACBD [010] (swap 2 and (2+1)=3)\r\nACDB [011] (swap 2 and (2+1)=3, and then 3 and (3+1)=4)\r\nADCB [020] (swap 2 and (2+2)=4)\r\nADBC [021] (swap 2 and (2+2)=4, and then 3 and (3+1)=4)\r\nBACD [100] (swap 1 and 1+1=2)\r\nBADC [101] (swap 1 and 1+1=2; 3 and 3+1=4)\r\nBCAD [110] (swap 1 and 1+1=2; 2 and 2+1=3)\r\nBCDA [111] (swap 1 and 1+1=2; 2 and 2+1=3; 3 and 3+1=4)\r\nBDCA [120] (swap 1 and 1+1=2; 2 and 2+2=4)\r\nBDAC [121] (swap 1 and 1+1=2; 2 and 2+2=4; 3 and 3+1=4)\r\nCBAD [200] (swap 1 and 1+2=3)\r\nCBDA [201] (swap 1 and 1+2=3; 3 and 3+1=4)\r\nCABD [210] (swap 1 and 1+2=3; 2 and 2+1=3)\r\nCADB [211] (swap 1 and 1+2=3; 2 and 2+1=3; 3 and 3+1=4)\r\nCDAB [220] (swap 1 and 1+2=3; 2 and 2+2=4)\r\nCDBA [221] (swap 1 and 1+2=3; 2 and 2+2=4; 3 and 3+1=4)\r\nDBCA [300] (swap 1 and 1+3=4)\r\nDBAC [301] (swap 1 and 1+3=4; 3 and 3+1=4)\r\nDCBA [310] (swap 1 and 1+3=4; 2 and 2+1=3)\r\nDCAB [311] (swap 1 and 1+3=4; 2 and 2+1=3; 3 and 3+1=4)\r\nDACB [320] (swap 1 and 1+3=4; 2 and 2+2=4)\r\nDABC [321] (swap 1 and 1+3=4; 2 and 2+2=4; 3 and 3+1=4)<\/pre>\n<p>If you add one, the entire counter rolls to 000, so we have enumerated every permutation.<\/p>\n<ul>\n<li>We always swap to the right, assuming that any work performed on the left side of the string is complete<\/li>\n<li>The maximum counter value for each position, given length (l) and position (p) is l-p.\u00a0 So in the 3rd position, 4-3=1, so position 3 can be 0 or 1.<\/li>\n<li>In the 4th position, len 4 &#8211; position 4 = 0, which is why we don&#8217;t need a 4th digit.<\/li>\n<\/ul>\n<p>We can take our counter code from above and modify it slightly:<\/p>\n<pre>int click(void){ \r\n    int p=len-1; \r\n\r\n    while(p&gt;=0) { \r\n        counter[p]++; \r\n\r\n        if(counter[p]&gt;=<span style=\"color: #00ff00;\">(len-p)<\/span>) { \r\n            counter[p]=0;\r\n            p--; \r\n        } else { \r\n            p=-2;\r\n        } \r\n    } \r\n\r\n    return(p+1); \r\n}<\/pre>\n<p>To build a permutation from our counter, we start with the original string, and then perform the swaps:<\/p>\n<pre>int len=4;\r\nchar *pstring=\"ABCD\"\r\nchar perm[len+1];\r\nint counter[len]={0};\r\n\r\nint click(void);\r\n\r\nvoid buildperm(void) {\r\n    int i;\r\n    char c;\r\n\r\n    <span style=\"color: #00ffff;\">\/* Populate the string from original *\/<\/span>\r\n    for(i=0;i&lt;len;i++) perm[i]=pstring[i];\r\n\r\n    for(i=0;i&lt;len;i++) if(counter[i]&gt;0) {\r\n        c                 =perm[i];\r\n        perm[i]           =perm[i+counter[i]];\r\n        perm[i+counter[i]]=c;\r\n    }\r\n}<\/pre>\n<p>If counter[i]=0, then it would swap with itself &#8211; counter[i+0].\u00a0 For counter[i]&gt;0, counter becomes the offset to the right &#8211; i+counter[i].<\/p>\n<p>Now, from our main program, we can call &#8216;click&#8217; to increment the counter, and &#8216;buildperm&#8217; to build a valid permutation from a given counter value.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"putting-it-all-together\"><\/span>Putting it All Together<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Here is the final version:<\/p>\n<pre>#include &lt;stdio.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n#include &lt;string.h&gt;\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Permutation String -- *\/<\/span>\r\nstatic char *pstring=\"ABCD\";\r\n\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Declare functions used later -- *\/<\/span>\r\nvoid  perminit(char *s);    \/* Initialize the poly counter array *\/\r\nint   permtick(void);        \/* Advance to the next permutation *\/\r\nvoid buildperm(char *s);    \/* Build current permutation from poly *\/\r\n\r\n<span style=\"color: #00ffff;\">\/* -- Global Variables -- *\/<\/span>\r\nchar *perm, *poly;\r\nint   plen;\r\n\r\n<span style=\"color: #00ffff;\">\/* -- -- MAIN -- -- *\/<\/span>\r\nvoid main(void){ \r\n\r\n    <span style=\"color: #00ffff;\">\/* Main code *\/<\/span>\r\n    printf(\"String: %s, %d chars\\n\\n\",pstring,strlen(pstring));\r\n\r\n    <span style=\"color: #00ffff;\">\/* Initialize the poly counter *\/<\/span>\r\n    <span style=\"color: #00ff00;\">perminit(pstring);<\/span>\r\n\r\n    do {\r\n        <span style=\"color: #00ffff;\">\/* Build current permutation from poly *\/<\/span>\r\n        <span style=\"color: #00ff00;\">buildperm(pstring);<\/span>\r\n\r\n        <span style=\"color: #00ff00;\">printf(\"Print from main loop: %s\\n\",perm);<\/span>\r\n\r\n        <span style=\"color: #00ffff;\">\/* Do some real work *\/\r\n\r\n        \/* The stack is lightweight because the entire\r\n        \/* state is held in poly, and there is no need \r\n        \/* for the function callback nonsense *\/<\/span>\r\n\r\n    <span style=\"color: #00ffff;\">\/* Permtick advances poly to the next permutation \r\n    \/* and returns 0 when there are none left *\/<\/span>\r\n\r\n    } while(<span style=\"color: #00ff00;\">permtick()<\/span>); \r\n}\r\n\r\n\r\n\r\nvoid perminit(char *s) {\r\n    <span style=\"color: #00ffff;\">\/* We have moved the init code to an init function,\r\n    \/* where it truly belongs *\/<\/span>\r\n\r\n    plen=strlen(s);\r\n    \r\n    perm=(char *)malloc((plen+1)*sizeof(char));\r\n    perm[plen]=0;\r\n\r\n    poly=(char *)malloc((plen+1)*sizeof(char));\r\n\r\n    <span style=\"color: #00ffff;\">\/* poly is a byte array that we are going to use as a big counter *\/<\/span>\r\n    int p;\r\n    for(p=0;p&lt;plen;p++) poly[p]=0; \r\n} \r\n\r\nint permtick(void) { \r\n    <span style=\"color: #00ffff;\">\/* Each time we call permtick, it increments our poly counter *\/<\/span> \r\n\r\n    int ret=-1;   <span style=\"color: #00ffff;\">\/* Return True by default *\/<\/span> \r\n    int p=plen-2; <span style=\"color: #00ffff;\">\/* Start at 2nd to last position *\/<\/span> \r\n\r\n    while( p &gt;= 0 ) {\r\n        <span style=\"color: #00ffff;\">\/* Increment poly digit *\/<\/span>\r\n        poly[p]++;        \r\n\r\n        <span style=\"color: #00ffff;\">\/* If poly digit exceeds plen-p, move to \r\n        \/* the next digit and loop *\/<\/span>\r\n        if(poly[p]&gt;=(plen-p)) {\r\n            poly[p]=0;    \r\n            p--;        \r\n\r\n            <span style=\"color: #00ffff;\">\/* FYI - this is why poly[plen-1] is always 0:\r\n            \/* That's it's maximum value, which is why we\r\n            \/* start at plen-2 *\/<\/span>\r\n        } else {\r\n            p=-2;        <span style=\"color: #00ffff;\">\/* Done looping *\/<\/span>\r\n        }\r\n    }\r\n\r\n    <span style=\"color: #00ffff;\">\/* All permutations have been calculated and p=-1 *\/<\/span>\r\n    if(p==-1) ret=0;\r\n\r\n    return(ret);\r\n}\r\n\r\n\r\nvoid buildperm(char *s) {\r\n    <span style=\"color: #00ffff;\">\/* Build a permutation from the poly counter *\/<\/span>\r\n\r\n    char c;\r\n    int i;\r\n\r\n    <span style=\"color: #00ffff;\">\/* Start with a fresh copy of the string *\/<\/span>\r\n    for(i=0;i&lt;plen;i++) perm[i]=s[i]; \r\n\r\n    <span style=\"color: #00ffff;\">\/* Swap digits based on each poly digit *\/<\/span> \r\n    <span style=\"color: #00ffff;\">\/* if poly[i]&gt;0 then swap with the (i+nth) digit *\/<\/span>\r\n    for(i=0;i&lt;(plen-1);i++) if(poly[i]&gt;0) {\r\n        c              =perm[i];\r\n        perm[i]        =perm[i+poly[i]];\r\n        perm[i+poly[i]]=c;\r\n    }  \r\n}\r\n<\/pre>\n<p>Now, we have fairly modular code without the need for recursion nor callbacks, that we could use for almost anything.<\/p>\n<p>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.\u00a0 perm[i] simply becomes an index in to an array of things:\u00a0 thing[perm[i]]<\/p>\n<p>For example:<\/p>\n<pre>int *pstring={1, 2, 3}\r\nint *perm, plen\r\n\r\nchar *thing={\"Apple\", \"Banana\", \"Orange\"}\r\n\r\n...\r\nbuildperm(pstring)\r\nfor(i=0;i&lt;plen;i++) printf(\"%s \",thing[perm[i]]);\r\n...<\/pre>\n<p>All of the other logic remains the same.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"conclusion\"><\/span>Conclusion<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Always avoid recursion.\u00a0 It&#8217;s slow and expensive.<\/p>\n<p>Here, we&#8217;ve reviewed a way to enumerate permutations while keeping your code agile and flexible.<\/p>\n<p>If you made it this far, thanks for hanging in there!\u00a0 I hope this helps you out!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>If you have a set of\u00a0things, a permutation is a specific way that you can list those things.\u00a0 Although algorithms exist to list every permutation, most of them rely on recursion &#8211; the calling of a function from within itself &#8211; which is horribly inefficient. If you want a non-recursive algorithm that lists every permutation, [&hellip;]<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,20],"tags":[],"class_list":["post-6056","post","type-post","status-publish","format-standard","hentry","category-good-design-bad-design","category-science"],"_links":{"self":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/6056","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/comments?post=6056"}],"version-history":[{"count":10,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/6056\/revisions"}],"predecessor-version":[{"id":6084,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/6056\/revisions\/6084"}],"wp:attachment":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/media?parent=6056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/categories?post=6056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/tags?post=6056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}