Here is a table to emphasize the point. A 26-character set is assumed.
- Length: Number of characters in each permutation
- Seconds: Computation time to generate all permutations of the given length
- Permutations: Number of unique ways to order the characters
Code: Select all
+--------+--------------+--------------------+
| Length | Seconds | Permutations |
+--------+--------------+--------------------+
| 1 | 0.0005 | 26 |
| 2 | 0.01 | 650 |
| 3 | 0.2 | 15 600 |
| 4 | 3 | 358 800 |
| 5 | 80 | 7 893 600 |
| 6 | xxx | 165 765 600 |
| 7 | xxxx | 3 315 312 000 |
| 8 | xxxxx | 62 990 928 000 |
| 9 | xxxxxx | 1 133 836 704 000 |
| 10 | xxxxxxx | 19 275 223 968 000 |
+--------+--------------+--------------------+
To put the number of seconds in perspective, here are some conversions.
Code: Select all
300 seconds = 5 minutes
3600 seconds = 1 hour
86400 seconds = 1 day
604800 seconds = 1 week
Writing a function to generate all permutations of more than a few characters is an exercise in futility. That's not an accusation--I actually have written such a function.
Anyway, to find the pattern, start with what you know. For instance, you know how to write a loop to generate a list of the 26 letters of the alphabet. Once you succeed with that, add a loop within the loop to concatenate two letters. You don't want the two letters to be the same, so you need a way to remember what you have used already. Try employing a variable to store the character at the first position. If the second character matches the first, skip it.
When you add a third loop inside the second, you will need to remember what characters are in the previous two positions. If the third character matches either the first or second, skip it. Now or later, using individual variables becomes cumbersome. Arrays are better suited for handling multiple related values. An array key should determine the character position. An array value is the character at that position.
You may notice that in the course of adding, modifying, and deleting the characters in the array, it is only the last character that ever changes. Because of this, we can call the array a "stack". To move to the next character position, "push" a character onto the stack. To move back to a previous character position, "pop" a character off the stack.
All of the loops appear pretty much the same, like a hall of mirrors. However, within the deepest inner loop, something a little different happens. Instead of a loop like the others, there is a loop to join the characters of the stack together to form a string which comprises a single permutation.
When you understand the pattern, you can simplify the code by writing a recursive function instead of the many nested loops. Besides making the code more compact, recursion allows you to have an arbitrary number of nested loops, and thus an arbitrary length of the resulting strings.