<p>How would I go about generating a list of all possible permutations of a string between x and y characters in length, containing a variable list of characters.</p>

<p>Any language would work, but it should be portable.</p>

[{'answer_id': 362, 'author': 'alumb', 'author_id': 80, 'author_profile': 'https://Stackoverflow.com/users/80', 'pm_score': 7, 'selected': True, 'text': '<p>There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)</p>\n\n<p>Some pseudocode:</p>\n\n<pre><code>list = originalString.split(\'\')\nindex = (0,0)\nlist = [""]\nfor iteration n in 1 to y:\n  index = (index[1], len(list))\n  for string s in list.subset(index[0] to end):\n    for character c in originalString:\n      list.add(s + c)\n</code></pre>\n\n<p>you\'d then need to remove all strings less than x in length, they\'ll be the first (x-1) * len(originalString) entries in the list.</p>\n'}, {'answer_id': 364, 'author': 'Mike Stone', 'author_id': 122, 'author_profile': 'https://Stackoverflow.com/users/122', 'pm_score': 3, 'selected': False, 'text': '<p>I just whipped this up quick in Ruby:</p>\n\n<pre><code>def perms(x, y, possible_characters)\n  all = [""]\n  current_array = all.clone\n  1.upto(y) { |iteration|\n    next_array = []\n    current_array.each { |string|\n      possible_characters.each { |c|\n        value = string + c\n        next_array.insert next_array.length, value\n        all.insert all.length, value\n      }\n    }\n    current_array = next_array\n  }\n  all.delete_if { |string| string.length &lt; x }\nend\n</code></pre>\n\n<p>You might look into language API for built in permutation type functions, and you might be able to write more optimized code, but if the numbers are all that high, I\'m not sure there is much of a way around having a lot of results.</p>\n\n<p>Anyways, the idea behind the code is start with string of length 0, then keep track of all the strings of length Z where Z is the current size in the iteration.  Then, go through each string and append each character onto each string.  Finally at the end, remove any that were below the x threshold and return the result.</p>\n\n<p>I didn\'t test it with potentially meaningless input (null character list, weird values of x and y, etc).</p>\n'}, {'answer_id': 388, 'author': 'Brian Willis', 'author_id': 118, 'author_profile': 'https://Stackoverflow.com/users/118', 'pm_score': 3, 'selected': False, 'text': '<p>I\'m not sure why you would want to do this in the first place. The resulting set for any moderately large values of x and y will be huge, and will grow exponentially as x and/or y get bigger. </p>\n\n<p>Lets say your set of possible characters is the 26 lowercase letters of the alphabet, and you ask your application to generate all permutations where length = 5. Assuming you don\'t run out of memory you\'ll get 11,881,376 (i.e. 26 to the power of 5) strings back. Bump that length up to 6, and you\'ll get 308,915,776 strings back. These numbers get painfully large, very quickly.</p>\n\n<p>Here\'s a solution I put together in Java. You\'ll need to provide two runtime arguments (corresponding to x and y). Have fun.</p>\n\n<pre><code>public class GeneratePermutations {\n    public static void main(String[] args) {\n        int lower = Integer.parseInt(args[0]);\n        int upper = Integer.parseInt(args[1]);\n\n        if (upper &lt; lower || upper == 0 || lower == 0) {\n            System.exit(0);\n        }\n\n        for (int length = lower; length &lt;= upper; length++) {\n            generate(length, "");\n        }\n    }\n\n    private static void generate(int length, String partial) {\n        if (length &lt;= 0) {\n            System.out.println(partial);\n        } else {\n            for (char c = \'a\'; c &lt;= \'z\'; c++) {\n                generate(length - 1, partial + c);\n            }\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 1910, 'author': 'nlucaroni', 'author_id': 157, 'author_profile': 'https://Stackoverflow.com/users/157', 'pm_score': 5, 'selected': False, 'text': '<p>You are going to get a lot of strings, that\'s for sure...</p>\n\n<p><img src="https://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D" alt="\\sum_{i=x}^y{\\frac{r!}{{(r-i)}!}}"><br>\nWhere x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly. You should definitely generate these as needed and not get sloppy and say, generate a powerset and then filter the length of strings.</p>\n\n<p>The following definitely isn\'t the best way to generate these, but it\'s an interesting aside, none-the-less.</p>\n\n<p>Knuth (volume 4, fascicle 2, 7.2.1.3) tells us that (s,t)-combination is equivalent to s+1 things taken t at a time with repetition -- an (s,t)-combination is notation used by Knuth that is equal to <img src="https://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D" alt="{t \\choose {s+t}">. We can figure this out by first generating each (s,t)-combination in binary form (so, of length (s+t)) and counting the number of 0\'s to the left of each 1.</p>\n\n<p>10001000011101 --> becomes the permutation: {0, 3, 4, 4, 4, 1}</p>\n'}, {'answer_id': 64961, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': '<p>In ruby:</p>\n\n<pre><code>str = "a"\n100_000_000.times {puts str.next!}\n</code></pre>\n\n<p>It is quite fast, but it is going to take some time =). Of course, you can start at "aaaaaaaa" if the short strings aren\'t interesting to you.</p>\n\n<p>I might have misinterpreted the actual question though - in one of the posts it sounded as if you just needed a bruteforce library of strings, but in the main question it sounds like you need to permutate a particular string.</p>\n\n<p>Your problem is somewhat similar to this one: <a href="http://beust.com/weblog/archives/000491.html" rel="nofollow noreferrer">http://beust.com/weblog/archives/000491.html</a> (list all integers in which none of the digits repeat themselves, which resulted in a whole lot of languages solving it, with the ocaml guy using permutations, and some java guy using yet another solution).</p>\n'}, {'answer_id': 69559, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 3, 'selected': False, 'text': '<p>This is a translation of Mike\'s Ruby version, into Common Lisp:</p>\n\n<pre><code>(defun perms (x y original-string)\n  (loop with all = (list "")\n        with current-array = (list "")\n        for iteration from 1 to y\n        do (loop with next-array = nil\n                 for string in current-array\n                 do (loop for c across original-string\n                          for value = (concatenate \'string string (string c))\n                          do (push value next-array)\n                             (push value all))\n                    (setf current-array (reverse next-array)))\n        finally (return (nreverse (delete-if #\'(lambda (el) (&lt; (length el) x)) all)))))\n</code></pre>\n\n<p>And another version, slightly shorter and using more loop facility features:</p>\n\n<pre><code>(defun perms (x y original-string)\n  (loop repeat y\n        collect (loop for string in (or (car (last sets)) (list ""))\n                      append (loop for c across original-string\n                                   collect (concatenate \'string string (string c)))) into sets\n        finally (return (loop for set in sets\n                              append (loop for el in set when (&gt;= (length el) x) collect el)))))\n</code></pre>\n'}, {'answer_id': 69612, 'author': 'nickf', 'author_id': 9021, 'author_profile': 'https://Stackoverflow.com/users/9021', 'pm_score': 0, 'selected': False, 'text': '<p>Though this doesn\'t answer your question exactly, here\'s one way to generate every permutation of the letters from a number of strings of the same length: eg, if your words were "coffee", "joomla" and "moodle", you can expect output like "coodle", "joodee", "joffle", etc.</p>\n\n<p>Basically, the number of combinations is the (number of words) to the power of (number of letters per word). So, choose a random number between 0 and the number of combinations - 1, convert that number to base (number of words), then use each digit of that number as the indicator for which word to take the next letter from.</p>\n\n<p>eg: in the above example. 3 words, 6 letters = 729 combinations. Choose a random number: 465. Convert to base 3: 122020. Take the first letter from word 1, 2nd from word 2, 3rd from word 2, 4th from word 0... and you get... "joofle".</p>\n\n<p>If you wanted all the permutations, just loop from 0 to 728. Of course, if you\'re just choosing one random value, a much <strike>simpler</strike> less-confusing way would be to loop over the letters. This method lets you avoid recursion, should you want all the permutations, plus it makes you look like you know Maths<sup>(tm)</sup>!</p>\n\n<p>If the number of combinations is excessive, you can break it up into a series of smaller words and concatenate them at the end.</p>\n'}, {'answer_id': 147211, 'author': 'Sarp Centel', 'author_id': 16622, 'author_profile': 'https://Stackoverflow.com/users/16622', 'pm_score': 3, 'selected': False, 'text': '<p>Recursive solution in C++    </p>\n\n<pre><code>int main (int argc, char * const argv[]) {\n        string s = "sarp";\n        bool used [4];\n        permute(0, "", used, s);\n}\n\nvoid permute(int level, string permuted, bool used [], string &amp;original) {\n    int length = original.length();\n\n    if(level == length) { // permutation complete, display\n        cout &lt;&lt; permuted &lt;&lt; endl;\n    } else {\n        for(int i=0; i&lt;length; i++) { // try to add an unused character\n            if(!used[i]) {\n                used[i] = true;\n                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string\n                used[i] = false;\n            }\n        }\n}\n</code></pre>\n'}, {'answer_id': 217209, 'author': 'Crackerjack', 'author_id': 13556, 'author_profile': 'https://Stackoverflow.com/users/13556', 'pm_score': 3, 'selected': False, 'text': '<p>Here is a simple word C# recursive solution:</p>\n\n<p><strong>Method:</strong></p>\n\n<pre><code>public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)\n        {\n            bool finished = true;\n            ArrayList newWords = new ArrayList();\n            if (words.Count == 0)\n            {\n                foreach (string letter in letters)\n                {\n                    words.Add(letter);\n                }\n            }\n\n            for(int j=index; j&lt;words.Count; j++)\n            {\n                string word = (string)words[j];\n                for(int i =0; i&lt;letters.Length; i++)\n                {\n                    if(!word.Contains(letters[i]))\n                    {\n                        finished = false;\n                        string newWord = (string)word.Clone();\n                        newWord += letters[i];\n                        newWords.Add(newWord);\n                    }\n                }\n            }\n\n            foreach (string newWord in newWords)\n            {   \n                words.Add(newWord);\n            }\n\n            if(finished  == false)\n            {\n                CalculateWordPermutations(letters, words, words.Count - newWords.Count);\n            }\n            return words;\n        }\n</code></pre>\n\n<p><strong>Calling:</strong></p>\n\n<pre><code>string[] letters = new string[]{"a","b","c"};\nArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);\n</code></pre>\n'}, {'answer_id': 291127, 'author': 'AShelly', 'author_id': 10396, 'author_profile': 'https://Stackoverflow.com/users/10396', 'pm_score': 4, 'selected': False, 'text': '<p>You might look at "<a href="http://applied-math.org/subset.pdf" rel="noreferrer">Efficiently Enumerating the Subsets of a Set</a>", which describes an algorithm to do part of what you want - quickly generate all subsets of N characters from length x to y.  It contains an implementation in C.  </p>\n\n<p>For each subset, you\'d still have to generate all the permutations.  For instance if you wanted 3 characters from "abcde", this algorithm would give you "abc","abd", "abe"...\nbut you\'d have to permute each one to get "acb", "bac", "bca", etc.</p>\n'}, {'answer_id': 550628, 'author': 'Chris Lutz', 'author_id': 60777, 'author_profile': 'https://Stackoverflow.com/users/60777', 'pm_score': 3, 'selected': False, 'text': '<p>In Perl, if you want to restrict yourself to the lowercase alphabet, you can do this:</p>\n\n<pre><code>my @result = ("a" .. "zzzz");\n</code></pre>\n\n<p>This gives all possible strings between 1 and 4 characters using lowercase characters. For uppercase, change <code>"a"</code> to <code>"A"</code> and <code>"zzzz"</code> to <code>"ZZZZ"</code>.</p>\n\n<p>For mixed-case it gets much harder, and probably not doable with one of Perl\'s builtin operators like that.</p>\n'}, {'answer_id': 2575419, 'author': 'Lazer', 'author_id': 113124, 'author_profile': 'https://Stackoverflow.com/users/113124', 'pm_score': 4, 'selected': False, 'text': '<p>Some working Java code based on <a href="https://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string/147211#147211">Sarp\'s answer</a>:</p>\n\n<pre><code>public class permute {\n\n    static void permute(int level, String permuted,\n                    boolean used[], String original) {\n        int length = original.length();\n        if (level == length) {\n            System.out.println(permuted);\n        } else {\n            for (int i = 0; i &lt; length; i++) {\n                if (!used[i]) {\n                    used[i] = true;\n                    permute(level + 1, permuted + original.charAt(i),\n                       used, original);\n                    used[i] = false;\n                }\n            }\n        }\n    }\n\n    public static void main(String[] args) {\n        String s = "hello";\n        boolean used[] = {false, false, false, false, false};\n        permute(0, "", used, s);\n    }\n}\n</code></pre>\n'}, {'answer_id': 3178268, 'author': 'Prakhar Gupta', 'author_id': 383513, 'author_profile': 'https://Stackoverflow.com/users/383513', 'pm_score': 4, 'selected': False, 'text': '<p>Here is a simple solution in C#.</p>\n\n<p>It generates only the distinct permutations of a given string.</p>\n\n<pre><code>    static public IEnumerable&lt;string&gt; permute(string word)\n    {\n        if (word.Length &gt; 1)\n        {\n\n            char character = word[0];\n            foreach (string subPermute in permute(word.Substring(1)))\n            {\n\n                for (int index = 0; index &lt;= subPermute.Length; index++)\n                {\n                    string pre = subPermute.Substring(0, index);\n                    string post = subPermute.Substring(index);\n\n                    if (post.Contains(character))\n                            continue;                       \n\n                    yield return pre + character + post;\n                }\n\n            }\n        }\n        else\n        {\n            yield return word;\n        }\n    }\n</code></pre>\n'}, {'answer_id': 4010695, 'author': 'Swapneel Patil', 'author_id': 251769, 'author_profile': 'https://Stackoverflow.com/users/251769', 'pm_score': 3, 'selected': False, 'text': '<pre><code>import java.util.*;\n\npublic class all_subsets {\n    public static void main(String[] args) {\n        String a = "abcd";\n        for(String s: all_perm(a)) {\n            System.out.println(s);\n        }\n    }\n\n    public static Set&lt;String&gt; concat(String c, Set&lt;String&gt; lst) {\n        HashSet&lt;String&gt; ret_set = new HashSet&lt;String&gt;();\n        for(String s: lst) {\n            ret_set.add(c+s);\n        }\n        return ret_set;\n    }\n\n    public static HashSet&lt;String&gt; all_perm(String a) {\n        HashSet&lt;String&gt; set = new HashSet&lt;String&gt;();\n        if(a.length() == 1) {\n            set.add(a);\n        } else {\n            for(int i=0; i&lt;a.length(); i++) {\n                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));\n            }\n        }\n        return set;\n    }\n}\n</code></pre>\n'}, {'answer_id': 4134431, 'author': 'rocksportrocker', 'author_id': 233813, 'author_profile': 'https://Stackoverflow.com/users/233813', 'pm_score': 4, 'selected': False, 'text': '<p>Non recursive solution according to Knuth, Python example:  </p>\n\n<pre><code>def nextPermutation(perm):\n    k0 = None\n    for i in range(len(perm)-1):\n        if perm[i]&lt;perm[i+1]:\n            k0=i\n    if k0 == None:\n        return None\n\n    l0 = k0+1\n    for i in range(k0+1, len(perm)):\n        if perm[k0] &lt; perm[i]:\n            l0 = i\n\n    perm[k0], perm[l0] = perm[l0], perm[k0]\n    perm[k0+1:] = reversed(perm[k0+1:])\n    return perm\n\nperm=list("12345")\nwhile perm:\n    print perm\n    perm = nextPermutation(perm)\n</code></pre>\n'}, {'answer_id': 4927100, 'author': 'Peyman', 'author_id': 556778, 'author_profile': 'https://Stackoverflow.com/users/556778', 'pm_score': 3, 'selected': False, 'text': "<p>... and here is the C version:</p>\n\n<pre><code>void permute(const char *s, char *out, int *used, int len, int lev)\n{\n    if (len == lev) {\n        out[lev] = '\\0';\n        puts(out);\n        return;\n    }\n\n    int i;\n    for (i = 0; i &lt; len; ++i) {\n        if (! used[i])\n            continue;\n\n        used[i] = 1;\n        out[lev] = s[i];\n        permute(s, out, used, len, lev + 1);\n        used[i] = 0;\n    }\n    return;\n}\n</code></pre>\n"}, {'answer_id': 5082432, 'author': 'raj', 'author_id': 628891, 'author_profile': 'https://Stackoverflow.com/users/628891', 'pm_score': 3, 'selected': False, 'text': '<blockquote>\n  <p>permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(<strong>*B</strong><em>C), (C</em><strong>B*</strong>)] -> [(<strong>*A</strong><em>BC), (B</em><strong>A</strong><em>C), (BC</em><strong>A*</strong>), (<strong>*A</strong><em>CB), (C</em><strong>A</strong><em>B), (CB</em><strong>A*</strong>)]\n  To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet (why? -exercise)</p>\n</blockquote>\n\n<pre><code>public static void main(String[] args) {\n\n    for (String str : permStr("ABBB")){\n        System.out.println(str);\n    }\n}\n\nstatic Vector&lt;String&gt; permStr(String str){\n\n    if (str.length() == 1){\n        Vector&lt;String&gt; ret = new Vector&lt;String&gt;();\n        ret.add(str);\n        return ret;\n    }\n\n    char start = str.charAt(0);\n    Vector&lt;String&gt; endStrs = permStr(str.substring(1));\n    Vector&lt;String&gt; newEndStrs = new Vector&lt;String&gt;();\n    for (String endStr : endStrs){\n        for (int j = 0; j &lt;= endStr.length(); j++){\n            if (endStr.substring(0, j).endsWith(String.valueOf(start)))\n                break;\n            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));\n        }\n    }\n    return newEndStrs;\n}\n</code></pre>\n\n<p>Prints all permutations sans duplicates</p>\n'}, {'answer_id': 6140144, 'author': 'Pedro', 'author_id': 482019, 'author_profile': 'https://Stackoverflow.com/users/482019', 'pm_score': 2, 'selected': False, 'text': '<p>This code in python, when called with <code>allowed_characters</code> set to <code>[0,1]</code> and 4 character max, would generate 2^4 results:</p>\n\n<p><code>[\'0000\', \'0001\', \'0010\', \'0011\', \'0100\', \'0101\', \'0110\', \'0111\', \'1000\', \'1001\', \'1010\', \'1011\', \'1100\', \'1101\', \'1110\', \'1111\']</code></p>\n\n<pre><code>def generate_permutations(chars = 4) :\n\n#modify if in need!\n    allowed_chars = [\n        \'0\',\n        \'1\',\n    ]\n\n    status = []\n    for tmp in range(chars) :\n        status.append(0)\n\n    last_char = len(allowed_chars)\n\n    rows = []\n    for x in xrange(last_char ** chars) :\n        rows.append("")\n        for y in range(chars - 1 , -1, -1) :\n            key = status[y]\n            rows[x] = allowed_chars[key] + rows[x]\n\n        for pos in range(chars - 1, -1, -1) :\n            if(status[pos] == last_char - 1) :\n                status[pos] = 0\n            else :\n                status[pos] += 1\n                break;\n\n    return rows\n\nimport sys\n\n\nprint generate_permutations()\n</code></pre>\n\n<p>Hope this is of use to you. Works with any character, not only numbers</p>\n'}, {'answer_id': 6922856, 'author': 'orion elenzil', 'author_id': 230851, 'author_profile': 'https://Stackoverflow.com/users/230851', 'pm_score': 3, 'selected': False, 'text': '<p>Here\'s a non-recursive version I came up with, in javascript.\nIt\'s not based on Knuth\'s non-recursive one above, although it has some similarities in element swapping.\nI\'ve verified its correctness for input arrays of up to 8 elements.</p>\n\n<p>A quick optimization would be pre-flighting the <code>out</code> array and avoiding <code>push()</code>.</p>\n\n<p>The basic idea is:</p>\n\n<ol>\n<li><p>Given a single source array, generate a first new set of arrays which swap the first element with each subsequent element in turn, each time leaving the other elements unperturbed.\neg: given 1234, generate 1234, 2134, 3214, 4231.</p></li>\n<li><p>Use each array from the previous pass as the seed for a new pass,\nbut instead of swapping the first element, swap the second element with each subsequent element. Also, this time, don\'t include the original array in the output.</p></li>\n<li><p>Repeat step 2 until done.</p></li>\n</ol>\n\n<p>Here is the code sample:</p>\n\n<pre><code>function oxe_perm(src, depth, index)\n{\n    var perm = src.slice();     // duplicates src.\n    perm = perm.split("");\n    perm[depth] = src[index];\n    perm[index] = src[depth];\n    perm = perm.join("");\n    return perm;\n}\n\nfunction oxe_permutations(src)\n{\n    out = new Array();\n\n    out.push(src);\n\n    for (depth = 0; depth &lt; src.length; depth++) {\n        var numInPreviousPass = out.length;\n        for (var m = 0; m &lt; numInPreviousPass; ++m) {\n            for (var n = depth + 1; n &lt; src.length; ++n) {\n                out.push(oxe_perm(out[m], depth, n));\n            }\n        }\n    }\n\n    return out;\n}\n</code></pre>\n'}, {'answer_id': 7625511, 'author': 'Anonymous Coward', 'author_id': 975258, 'author_profile': 'https://Stackoverflow.com/users/975258', 'pm_score': 2, 'selected': False, 'text': '<p>I needed this today, and although the answers already given pointed me in the right direction, they weren\'t quite what I wanted.</p>\n\n<p>Here\'s an implementation using Heap\'s method. The length of the array must be at least 3 and for practical considerations not be bigger than 10 or so, depending on what you want to do, patience and clock speed.</p>\n\n<p>Before you enter your loop, initialise <code>Perm(1 To N)</code> with the first permutation, <code>Stack(3 To N)</code> with zeroes*, and <code>Level</code> with <code>2</code>**. At the end of the loop call <code>NextPerm</code>,  which will return false when we\'re done.</p>\n\n<p>* VB will do that for you.</p>\n\n<p>** You can change NextPerm a little to make this unnecessary, but it\'s clearer like this.</p>\n\n<pre class="lang-vb prettyprint-override"><code>Option Explicit\n\nFunction NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean\nDim N As Long\nIf Level = 2 Then\n    Swap Perm(1), Perm(2)\n    Level = 3\nElse\n    While Stack(Level) = Level - 1\n        Stack(Level) = 0\n        If Level = UBound(Stack) Then Exit Function\n        Level = Level + 1\n    Wend\n    Stack(Level) = Stack(Level) + 1\n    If Level And 1 Then N = 1 Else N = Stack(Level)\n    Swap Perm(N), Perm(Level)\n    Level = 2\nEnd If\nNextPerm = True\nEnd Function\n\nSub Swap(A As Long, B As Long)\nA = A Xor B\nB = A Xor B\nA = A Xor B\nEnd Sub\n\n\'This is just for testing.\nPrivate Sub Form_Paint()\nConst Max = 8\nDim A(1 To Max) As Long, I As Long\nDim S(3 To Max) As Long, J As Long\nDim Test As New Collection, T As String\nFor I = 1 To UBound(A)\n    A(I) = I\nNext\nCls\nScaleLeft = 0\nJ = 2\nDo\n    If CurrentY + TextHeight("0") &gt; ScaleHeight Then\n        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)\n        CurrentY = 0\n        CurrentX = 0\n    End If\n    T = vbNullString\n    For I = 1 To UBound(A)\n        Print A(I);\n        T = T &amp; Hex(A(I))\n    Next\n    Print\n    Test.Add Null, T\nLoop While NextPerm(A, S, J)\nJ = 1\nFor I = 2 To UBound(A)\n    J = J * I\nNext\nIf J &lt;&gt; Test.Count Then Stop\nEnd Sub\n</code></pre>\n\n<p>Other methods are described by various authors. Knuth describes two, one gives lexical order, but is complex and slow, the other is known as the method of plain changes. Jie Gao and Dianjun Wang also wrote an interesting paper.</p>\n'}, {'answer_id': 8808091, 'author': 'Unnykrishnan S', 'author_id': 1141488, 'author_profile': 'https://Stackoverflow.com/users/1141488', 'pm_score': 5, 'selected': False, 'text': '<p>It\'s better to use backtracking</p>\n\n\n\n<pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;\n#include &lt;string.h&gt;\n\nvoid swap(char *a, char *b) {\n    char temp;\n    temp = *a;\n    *a = *b;\n    *b = temp;\n}\n\nvoid print(char *a, int i, int n) {\n    int j;\n    if(i == n) {\n        printf("%s\\n", a);\n    } else {\n        for(j = i; j &lt;= n; j++) {\n            swap(a + i, a + j);\n            print(a, i + 1, n);\n            swap(a + i, a + j);\n        }\n    }\n}\n\nint main(void) {\n    char a[100];\n    gets(a);\n    print(a, 0, strlen(a) - 1);\n    return 0;\n}\n</code></pre>\n'}, {'answer_id': 10238654, 'author': 'Kem Mason', 'author_id': 398582, 'author_profile': 'https://Stackoverflow.com/users/398582', 'pm_score': 3, 'selected': False, 'text': '<p>Ruby answer that works:</p>\n\n<pre><code>class String\n  def each_char_with_index\n    0.upto(size - 1) do |index|\n      yield(self[index..index], index)\n    end\n  end\n  def remove_char_at(index)\n    return self[1..-1] if index == 0\n    self[0..(index-1)] + self[(index+1)..-1]\n  end\nend\n\ndef permute(str, prefix = \'\')\n  if str.size == 0\n    puts prefix\n    return\n  end\n  str.each_char_with_index do |char, index|\n    permute(str.remove_char_at(index), prefix + char)\n  end\nend\n\n# example\n# permute("abc")\n</code></pre>\n'}, {'answer_id': 11672570, 'author': 'wliao', 'author_id': 150607, 'author_profile': 'https://Stackoverflow.com/users/150607', 'pm_score': 0, 'selected': False, 'text': '<p>c# iterative:</p>\n\n<pre><code>public List&lt;string&gt; Permutations(char[] chars)\n    {\n        List&lt;string&gt; words = new List&lt;string&gt;();\n        words.Add(chars[0].ToString());\n        for (int i = 1; i &lt; chars.Length; ++i)\n        {\n            int currLen = words.Count;\n            for (int j = 0; j &lt; currLen; ++j)\n            {\n                var w = words[j];\n                for (int k = 0; k &lt;= w.Length; ++k)\n                {\n                    var nstr = w.Insert(k, chars[i].ToString());\n                    if (k == 0)\n                        words[j] = nstr;\n                    else\n                        words.Add(nstr);\n                }\n            }\n        }\n        return words;\n    }\n</code></pre>\n'}, {'answer_id': 17182840, 'author': 'Ramy', 'author_id': 796477, 'author_profile': 'https://Stackoverflow.com/users/796477', 'pm_score': 3, 'selected': False, 'text': '<p>The following Java recursion prints all permutations of a given string:</p>\n\n<pre><code>//call it as permut("",str);\n\npublic void permut(String str1,String str2){\n    if(str2.length() != 0){\n        char ch = str2.charAt(0);\n        for(int i = 0; i &lt;= str1.length();i++)\n            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),\n                     str2.substring(1,str2.length()));\n    }else{\n    System.out.println(str1);\n    }\n}\n</code></pre>\n\n<p>Following is the updated version of above "permut" method which makes n! (n factorial) less recursive calls compared to the above method</p>\n\n<pre><code>//call it as permut("",str);\n\npublic void permut(String str1,String str2){\n   if(str2.length() &gt; 1){\n       char ch = str2.charAt(0);\n       for(int i = 0; i &lt;= str1.length();i++)\n          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),\n                 str2.substring(1,str2.length()));\n   }else{\n    char ch = str2.charAt(0);\n    for(int i = 0; i &lt;= str1.length();i++)\n        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),\n                 str2.substring(1,str2.length()));\n   }\n}\n</code></pre>\n'}, {'answer_id': 17480974, 'author': 'Winster', 'author_id': 1440435, 'author_profile': 'https://Stackoverflow.com/users/1440435', 'pm_score': 0, 'selected': False, 'text': "<p>A recursive solution in python. The good thing about this code is that it exports a dictionary, with keys as strings and all possible permutations as values. All possible string lengths are included, so in effect, you are creating a superset.</p>\n\n<p>If you only require the final permutations, you can delete other keys from the dictionary.</p>\n\n<p>In this code, the dictionary of permutations is global.</p>\n\n<p>At the base case, I store the value as both possibilities in a list. <code>perms['ab'] = ['ab','ba']</code>.</p>\n\n<p>For higher string lengths, the function refers to lower string lengths and incorporates the previously calculated permutations.</p>\n\n<p>The function does two things:</p>\n\n<ul>\n<li>calls itself with a smaller string</li>\n<li>returns a list of permutations of a particular string if already available. If returned to itself, these will be used to append to the character and create newer permutations.</li>\n</ul>\n\n<p>Expensive for memory. </p>\n\n<pre><code>perms = {}\ndef perm(input_string):\n    global perms\n    if input_string in perms:\n        return perms[input_string] # This will send a list of all permutations\n    elif len(input_string) == 2:\n        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]\n        return perms[input_string]\n    else:\n        perms[input_string] = []\n        for index in range(0, len(input_string)):\n            new_string = input_string[0:index] + input_string[index +1:]\n            perm(new_string)\n            for entries in perms[new_string]:\n                perms[input_string].append(input_string[index] + entries)\n    return perms[input_string]\n</code></pre>\n"}, {'answer_id': 18387484, 'author': 'abkds', 'author_id': 2537745, 'author_profile': 'https://Stackoverflow.com/users/2537745', 'pm_score': 0, 'selected': False, 'text': "<pre><code>def gen( x,y,list): #to generate all strings inserting y at different positions\nlist = []\nlist.append( y+x )\nfor i in range( len(x) ):\n    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )\nreturn list \n\ndef func( x,i,j ): #returns x[i..j]\nz = '' \nfor i in range(i,j+1):\n    z = z+x[i]\nreturn z \n\ndef perm( x , length , list ): #perm function\nif length == 1 : # base case\n    list.append( x[len(x)-1] )\n    return list \nelse:\n    lists = perm( x , length-1 ,list )\n    lists_temp = lists #temporarily storing the list \n    lists = []\n    for i in range( len(lists_temp) ) :\n        list_temp = gen(lists_temp[i],x[length-2],lists)\n        lists += list_temp \n    return lists\n</code></pre>\n"}, {'answer_id': 19461362, 'author': 'Neo', 'author_id': 2263483, 'author_profile': 'https://Stackoverflow.com/users/2263483', 'pm_score': 0, 'selected': False, 'text': '<p>Recursive Solution with driver <code>main()</code> method.</p>\n\n<pre><code>public class AllPermutationsOfString {\npublic static void stringPermutations(String newstring, String remaining) {\n    if(remaining.length()==0)\n        System.out.println(newstring);\n\n    for(int i=0; i&lt;remaining.length(); i++) {\n        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");\n        stringPermutations(newstring+remaining.charAt(i), newRemaining);\n    }\n}\n\npublic static void main(String[] args) {\n    String string = "abc";\n    AllPermutationsOfString.stringPermutations("", string); \n}\n</code></pre>\n\n<p>}</p>\n'}, {'answer_id': 20993674, 'author': 'gd1', 'author_id': 671092, 'author_profile': 'https://Stackoverflow.com/users/671092', 'pm_score': 4, 'selected': False, 'text': '<p>There are a lot of good answers here. I also suggest a very simple recursive solution in C++.</p>\n\n<pre><code>#include &lt;string&gt;\n#include &lt;iostream&gt;\n\ntemplate&lt;typename Consume&gt;\nvoid permutations(std::string s, Consume consume, std::size_t start = 0) {\n    if (start == s.length()) consume(s);\n    for (std::size_t i = start; i &lt; s.length(); i++) {\n        std::swap(s[start], s[i]);\n        permutations(s, consume, start + 1);\n    }\n}\n\nint main(void) {\n    std::string s = "abcd";\n    permutations(s, [](std::string s) {\n        std::cout &lt;&lt; s &lt;&lt; std::endl;\n    });\n}\n</code></pre>\n\n<p><strong>Note</strong>: strings with repeated characters will not produce unique permutations.</p>\n'}, {'answer_id': 21298759, 'author': 'Paté', 'author_id': 474321, 'author_profile': 'https://Stackoverflow.com/users/474321', 'pm_score': 0, 'selected': False, 'text': "<pre><code>def permutation(str)\n  posibilities = []\n  str.split('').each do |char|\n    if posibilities.size == 0\n      posibilities[0] = char.downcase\n      posibilities[1] = char.upcase\n    else\n      posibilities_count = posibilities.length\n      posibilities = posibilities + posibilities\n      posibilities_count.times do |i|\n        posibilities[i] += char.downcase\n        posibilities[i+posibilities_count] += char.upcase\n      end\n    end\n  end\n  posibilities\nend\n</code></pre>\n\n<p>Here is my take on a non recursive version</p>\n"}, {'answer_id': 21765529, 'author': 'Nipun Talukdar', 'author_id': 1898070, 'author_profile': 'https://Stackoverflow.com/users/1898070', 'pm_score': 2, 'selected': False, 'text': '<p>Here is a link that describes how to print permutations of a string. \n<a href="http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html" rel="nofollow">http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html</a></p>\n'}, {'answer_id': 24720609, 'author': 'Abdul Fatir', 'author_id': 2605733, 'author_profile': 'https://Stackoverflow.com/users/2605733', 'pm_score': 0, 'selected': False, 'text': "<p>The pythonic solution:  </p>\n\n<pre><code>from itertools import permutations\ns = 'ABCDEF'\np = [''.join(x) for x in permutations(s)]\n</code></pre>\n"}, {'answer_id': 31086857, 'author': 'Adilli Adil', 'author_id': 2172507, 'author_profile': 'https://Stackoverflow.com/users/2172507', 'pm_score': 0, 'selected': False, 'text': '<p>Well here is an elegant, non-recursive, O(n!) solution:</p>\n\n<pre><code>public static StringBuilder[] permutations(String s) {\n        if (s.length() == 0)\n            return null;\n        int length = fact(s.length());\n        StringBuilder[] sb = new StringBuilder[length];\n        for (int i = 0; i &lt; length; i++) {\n            sb[i] = new StringBuilder();\n        }\n        for (int i = 0; i &lt; s.length(); i++) {\n            char ch = s.charAt(i);\n            int times = length / (i + 1);\n            for (int j = 0; j &lt; times; j++) {\n                for (int k = 0; k &lt; length / times; k++) {\n                    sb[j * length / times + k].insert(k, ch);\n                }\n            }\n        }\n        return sb;\n    }\n</code></pre>\n'}, {'answer_id': 37639997, 'author': 'Achilles Ram Nakirekanti', 'author_id': 3052383, 'author_profile': 'https://Stackoverflow.com/users/3052383', 'pm_score': 0, 'selected': False, 'text': '<p>code written for java language :</p>\n\n<p>package namo.algorithms;</p>\n\n<p>import java.util.Scanner;</p>\n\n<p>public class Permuations {  </p>\n\n<pre><code>public static int totalPermutationsCount = 0;\n    public static void main(String[] args) {\n\n        Scanner sc = new Scanner(System.in);\n        System.out.println("input string : ");\n        String inputString = sc.nextLine();\n        System.out.println("given input String ==&gt; "+inputString+ " :: length is = "+inputString.length());\n        findPermuationsOfString(-1, inputString);\n        System.out.println("**************************************");\n        System.out.println("total permutation strings ==&gt; "+totalPermutationsCount);\n    }\n\n\n    public  static void findPermuationsOfString(int fixedIndex, String inputString) {\n        int currentIndex = fixedIndex +1;\n\n        for (int i = currentIndex; i &lt; inputString.length(); i++) {\n            //swap elements and call the findPermuationsOfString()\n\n            char[] carr = inputString.toCharArray();\n            char tmp = carr[currentIndex];\n            carr[currentIndex] = carr[i];\n            carr[i] = tmp;\n            inputString =  new String(carr);\n\n            //System.out.println("chat At : current String ==&gt; "+inputString.charAt(currentIndex));\n            if(currentIndex == inputString.length()-1) {\n                totalPermutationsCount++;\n                System.out.println("permuation string ==&gt; "+inputString);\n            } else {\n                //System.out.println("in else block&gt;&gt;&gt;&gt;");\n                findPermuationsOfString(currentIndex, inputString);\n                 char[] rarr = inputString.toCharArray();\n                    char rtmp = carr[i];\n                    carr[i] = carr[currentIndex];\n                    carr[currentIndex] = rtmp;\n                    inputString =  new String(carr);\n            }\n        }\n    }\n</code></pre>\n\n<p>}</p>\n'}, {'answer_id': 42061222, 'author': 'Naresh Dhiman', 'author_id': 2130204, 'author_profile': 'https://Stackoverflow.com/users/2130204', 'pm_score': -1, 'selected': False, 'text': '<p>The possible string permutations can be computed using recursive function. Below is one of the possible solution.</p>\n\n<pre><code>public static String insertCharAt(String s, int index, char c) {\n        StringBuffer sb = new StringBuffer(s);\n        StringBuffer sbb = sb.insert(index, c);\n        return sbb.toString();\n}\n\npublic static ArrayList&lt;String&gt; getPerm(String s, int index) {\n        ArrayList&lt;String&gt; perm = new ArrayList&lt;String&gt;();\n\n        if (index == s.length()-1) {\n            perm.add(String.valueOf(s.charAt(index)));\n            return perm;\n        }\n\n        ArrayList&lt;String&gt; p = getPerm(s, index+1);\n        char c = s.charAt(index);\n\n        for(String pp : p) {\n            for (int idx=0; idx&lt;pp.length()+1; idx++) {\n                String ss = insertCharAt(pp, idx, c);\n                perm.add(ss);\n            }\n        }\n\n        return perm;    \n}\n\npublic static void testGetPerm(String s) {\n        ArrayList&lt;String&gt; perm = getPerm(s,0);\n        System.out.println(s+" --&gt; total permutation are :: "+perm.size());\n        System.out.println(perm.toString());\n}\n</code></pre>\n'}, {'answer_id': 63979467, 'author': 'mourya venkat', 'author_id': 7522482, 'author_profile': 'https://Stackoverflow.com/users/7522482', 'pm_score': 1, 'selected': False, 'text': '<p>Recursive Approach</p>\n<pre><code>func StringPermutations(inputStr string) (permutations []string) {\n    for i := 0; i &lt; len(inputStr); i++ {\n        inputStr = inputStr[1:] + inputStr[0:1]\n        if len(inputStr) &lt;= 2 {\n            permutations = append(permutations, inputStr)\n            continue\n        }\n        leftPermutations := StringPermutations(inputStr[0 : len(inputStr)-1])\n        for _, leftPermutation := range leftPermutations {\n            permutations = append(permutations, leftPermutation+inputStr[len(inputStr)-1:])\n        }\n    }\n    return\n}\n</code></pre>\n'}, {'answer_id': 66228704, 'author': 'Bhaskar13', 'author_id': 11930483, 'author_profile': 'https://Stackoverflow.com/users/11930483', 'pm_score': 2, 'selected': False, 'text': '<p>Many of the previous answers used backtracking. This is the <strong>asymptotically optimal way O(n*n!) of generating permutations</strong> after initial sorting</p>\n<pre><code>class Permutation {\n\n    /* runtime -O(n) for generating nextPermutaion\n     * and O(n*n!) for generating all n! permutations with increasing sorted array as start\n     * return true, if there exists next lexicographical sequence\n     * e.g [a,b,c],3-&gt; true, modifies array to [a,c,b]\n     * e.g [c,b,a],3-&gt; false, as it is largest lexicographic possible */\n    public static boolean nextPermutation(char[] seq, int len) {\n        // 1\n        if (len &lt;= 1)\n            return false;// no more perm\n        // 2: Find last j such that seq[j] &lt;= seq[j+1]. Terminate if no such j exists\n        int j = len - 2;\n        while (j &gt;= 0 &amp;&amp; seq[j] &gt;= seq[j + 1]) {\n            --j;\n        }\n        if (j == -1)\n            return false;// no more perm\n        // 3: Find last l such that seq[j] &lt;= seq[l], then exchange elements j and l\n        int l = len - 1;\n        while (seq[j] &gt;= seq[l]) {\n            --l;\n        }\n        swap(seq, j, l);\n        // 4: Reverse elements j+1 ... count-1:\n        reverseSubArray(seq, j + 1, len - 1);\n        // return seq, add store next perm\n\n        return true;\n    }\n    private static void swap(char[] a, int i, int j) {\n        char temp = a[i];\n        a[i] = a[j];\n        a[j] = temp;\n    }\n\n    private static void reverseSubArray(char[] a, int lo, int hi) {\n        while (lo &lt; hi) {\n            swap(a, lo, hi);\n            ++lo;\n            --hi;\n        }\n    }\n    public static void main(String[] args) {\n        String str = &quot;abcdefg&quot;;\n        char[] array = str.toCharArray();\n        Arrays.sort(array);\n        int cnt=0;\n        do {\n            System.out.println(new String(array));\n            cnt++;\n        }while(nextPermutation(array, array.length));\n        System.out.println(cnt);//5040=7!\n    }\n    //if we use &quot;bab&quot;-&gt; &quot;abb&quot;, &quot;bab&quot;, &quot;bba&quot;, 3(#permutations)\n}\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/361', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/115/']