StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>OPTION 1</p> <p>One option would be to use 256 bits of storage on the stack to store a bitmask of which characters you had tried in the for loop, and only to recurse for new characters.</p> <p>OPTION 2</p> <p>A second option is to use the approach suggested in the comments ( <a href="http://n1b-algo.blogspot.com/2009/01/string-permutations.html" rel="nofollow">http://n1b-algo.blogspot.com/2009/01/string-permutations.html</a>) and change the for loop to:</p> <pre><code>else { char last=0; for(int i = 0; i < range; ++i) { if (last==set[begin+i]) continue; last = set[begin+i]; swap(&set[begin], &set[begin+i]); permute(set, begin+1, end); swap(&set[begin], &set[begin+i]); } } </code></pre> <p>However, to use this approach you will also have to sort the characters set[begin],set[begin+1],...set[end-1] at the entry to the function.</p> <p>Note that you have to sort every time the function is called. (The blog post does not seem to mention this, but otherwise you will generate too many results for an input string "aabbc". The problem is that the string does not stay sorted after swap is used.)</p> <p>This is still not very efficient. For example, for a string containing 1 'a' and N 'b's this approach will end up calling the sort N times for an overall complexity of N^2logN</p> <p>OPTION 3</p> <p>A more efficient approach for long strings containing lots of repeats would be to maintain both the string "set" and a dictionary of how many of each type of character you have left to use. The for loop would change to a loop over the keys of the dictonary as these would be the unique characters that are allowed at that position.</p> <p>This would have complexity equal to the number of output strings, and only a very small extra amount of storage to hold the dictionary.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload