Finding Permutations�Easier and Faster

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.



About the Author

Srinivasan Muthuswamy Sivaraman

Working on Java/C++/C/Windows/Linux technologies Hobbies: playing with numbers.

Downloads

Comments

  • Impressed

    Posted by Shivinder Singh Narr on 03/12/2013 11:59am

    Hey, I have implemented your algorithm of permutation. It creates all permutations of a string. It was a great idea. If you observe, it's time complexity is very less than traditional methods. I am saying this because I have used inbuilt permutation function in python. I analysed the time and observed that This algorithm implemented in C, requires less time than other methods. According to my program, it's time complexity is O(n^4). If you have anything to share about much more faster algorithm than this, please reply to my email address.

    Reply
  • backlinks

    Posted by backlinks on 09/05/2012 11:17pm

    Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You obviously know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something informative to read?

    Reply
  • try

    Posted by try on 07/13/2012 01:41pm

    try...

    Reply
  • solution

    Posted by naveen kumar on 07/13/2012 01:39pm

    Ex : 1234 rotate once right ... 4123,3412,2341,1234. reverse these numbers.. 3214,2143,1432,4321. Fix first digit of original number and rotate rest to right we get 1423... apply same algo. here. 3142,2314,4231,1423. reverse these number... 2413,4132,1324,3241. Rotate last time 1342 (Total rotations length-1 times).. 2134,4213,3421,1342.. reverse.. 4312,3124,1243,2431. Final Answere 24 values : 4123,3412,2341,1234. 3214,2143,1432,4321. 3142,2314,4231,1423. 2413,4132,1324,3241. 2134,4213,3421,1342. 4312,3124,1243,2431.

    Reply
  • good algo

    Posted by mail_suka@rediffmail.com on 07/15/2004 11:24am

    hi, nice algo. btw, here is a interesting prob for u. how many ways, we can arrange 1 to n (n can be 10, 100 or 1000, any number) so that no number comes in its original position? (meaning 2 shud not appear in 2nd position, after arrangement). consider space, time comlpexity when u design the algo. regards;

    Reply
  • Good one

    Posted by kandukondein on 07/10/2004 02:28pm

    Hey Thats a good one. A good tutorial for beginners. Regards;

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: November 20, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Are you wanting to target two or more platforms such as iOS, Android, and/or Windows? You are not alone. 90% of enterprises today are targeting two or more platforms. Attend this eSeminar to discover how mobile app developers can rely on one IDE to create applications across platforms and approaches (web, native, and/or hybrid), saving time, money, and effort and introducing apps to market faster. You'll learn the trade-offs for gaining long …

  • Live Event Date: November 18, 2014 @ 11:00 a.m. EST As you embrace the hybrid world of on-premise and cloud applications, often accessed via mobile devices, you now have to be concerned that cybercriminals have yet another vehicle to attack your business. In fact, the average cost of cybercrime has increased over 10% in the last year, and this applies to businesses of all sizes. Attend this webinar to hear David Monahan, Security Research Director at EMA, and Dana Epp, recognized security luminary from …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds