Bell Algorithm for Permutation

This Permutation algorithm is pretty simple. We have to swap the items in such a way that the order of consecutive swaps forms a series of inverted and straight bells, as shown in the figure :

Permutation Algorithm

This can be better understood by taking an example.
Lets say we have to find all the permutations of the numbers 1, 2, 3, 4 using Bell Permutation Algorithm. The sequence of swapping will follow the sequence :
1  2  2  2  3  3  3  1
2  1  3  3  2  2  1  3
3  3  1  4  4  1  2  2
4  4  4  1  1  4  4  4     forming the first bell :

Permutation AlgorithmFigured out an inverted bell..?

The swapping will thus continue to form the 2nd bell, which will be straight.

1  2  2  2  3  3  3  1  1  3  3  3
2  1  3  3  2  2  1  3  3  1  4  4
3  3  1  4  4  1  2  2  4  4  1  2
4  4  4  1  1  4  4  4  2  2  2  1

Permutation AlgorithmContinuing and forming the 3rd bell (inverted) :

1  2  2  2  3  3  3  1  1  3  3  3  4  4  4  1
2  1  3  3  2  2  1  3  3  1  4  4  3  3  1  4
3  3  1  4  4  1  2  2  4  4  1  2  2  1  3  3
4  4  4  1  1  4  4  4  2  2  2  1  1  2  2  2

Permutation Algorithm

Forming the 4th bell (straight) :

1  2  2  2  3  3  3  1  1  3  3  3  4  4  4  1  1  4  4  4
2  1  3  3  2  2  1  3  3  1  4  4  3  3  1  4  4  1  2  2
3  3  1  4  4  1  2  2  4  4  1  2  2  1  3  3  2  2  1  3
4  4  4  1  1  4  4  4  2  2  2  1  1  2  2  2  3  3  3  1

Permutation AlgorithmFinally forming the last bell, showing all the 24 permutations :

1  2  2  2  3  3  3  1  1  3  3  3  4  4  4  1  1  4  4  4  2  2  2  1
2  1  3  3  2  2  1  3  3  1  4  4  3  3  1  4  4  1  2  2  4  4  1  2
3  3  1  4  4  1  2  2  4  4  1  2  2  1  3  3  2  2  1  3  3  1  4  4
4  4  4  1  1  4  4  4  2  2  2  1  1  2  2  2  3  3  3  1  1  3  3  3

Permutation Algorithm


Related Posts

Share

Filed Under: Algorithms

About the Author: Software Engineer - Advanced Search & Recommendation at Rovi

RSSComments (1)

Leave a Reply | Trackback URL

  1. loans says:

    I want to thank the blogger very much not only for this post but also for his all previous efforts. I found programminggeeks.com to be very interesting. I will be coming back to programminggeeks.com for more information.

Leave a Reply

*

AWSOM Powered