Finding Permutations—Easier and Faster
Environment: C++, any version that supports namespaces
Introduction
This article explains the technique of finding permutations in a simple and fast manner. It also provides the source code for the same.
Explanation
For a given string of length N, there are actually N! Permutations. The technique we apply here is to find the unique of those permutations and display them.
Let’s take this string: 123. If we rotate this string in a circular manner, we get 231 and 312. The point here is, if we find 1 string of the N! Permutations, we can produce N permutations by rotating it circularly. This reduces the time, which is proportional to N. The greater the value of N, the more the algorithm is optimized.
In short, the algorithm finds a number and rotates the number circularly N times to get N numbers.
Lets apply the algorithm. Lets take string {12} of length 2 (N=2). The unique pattern is 12 and if we rotate we get 21.
Let’s take the string {123} of length 3 (N=3). The unique patterns are as follows:
1(23): 123 is unique pattern resulting in (123)
1(32): Rotate the pattern (23) u get another pattern (32) resulting in a pattern (132)
(231): By rotating the pattern (123)
(312): By rotating the pattern (123)
(321): By rotating the pattern (132)
(213): By rotating the pattern (132)
The output patterns are:
| Level 1 | Level 2 | Permutations |
| 123 | ||
| 1(23) | 123 | |
| 231 | ||
| 312 | ||
| 1(32) | 132 | |
| 321 | ||
| 213 |
If we apply the same algorithm for the string {1234} of length 4 (N=4), the patterns are as below:
| Level 1 | Level 2 | Level 3 | Permutations |
| 1234 | |||
| 12(34) | |||
| 1(234) | 1234 | ||
| 2341 | |||
| 3412 | |||
| 4123 | |||
| 1(342) | 1342 | ||
| 3421 | |||
| 4213 | |||
| 2134 | |||
| 1(423) | 1423 | ||
| 4231 | |||
| 2314 | |||
| 3142 | |||
| 12(43) | |||
| 1(243) | 1243 | ||
| 2431 | |||
| 4312 | |||
| 3124 | |||
| 1(432) | 1432 | ||
| 4321 | |||
| 3214 | |||
| 2143 | |||
| 1(324) | 1324 | ||
| 3241 | |||
| 2413 | |||
| 4132 |
Comparison
The traditional algorithm goes and finds all the permutations where, as in this algorithm, we find only the unique permutation and produce the other permutations by rotating the original permutation in a circular manner.
Conclusion
The algorithm finds only the unique numbers and finds the other (N) permutations by rotating the original permutation circularly. Hence, it increases the performance.
