That's a picture of me in Baldwin Hills, Santa Monica
Bangalore based engineer currently helping SMEs grow via SMERGERS. Interested in Programming, Design, Startups and a few other things. MS-CS @USC, Los Angeles, BE @BMSCE.
I can be reached on
krishna [at] krishnabharadwaj [dot] info
Here are some of my other online profiles
Powered by Python and Django
kb
Geek, Programmer, FOSS Enthusiast, MS CS @USC. Loves Python / Django. Co-founder @ SMERGERS, Previously at Google, BlockBeacon, NI R&D

Apart from Johnson trotter, Permutations can be generated in many ways. The two methods i'll be discussing here are :

1. Recursive Method
2. Minimal Change Method or Bottom up approach.

1. Recursive Method

In this method, we take out a character at position 'I' and permute the rest of the string recursively. It goes something like this.. Lets say
"abc" is the string.

a + permute("bc") = abc & acb
b + permute("ac") = bac & bca
c + permute("ab") = cab & cba

There by generating all the permutations.

2. Minimal Change Method or Bottom up approach.
In this method, we start from a single character, append a new character and rotate the newly appended character covering all positions in the string. Like this..

a
ab, ba
abc,acb,cab,bac,bca,cba


blog comments powered by Disqus