flat assembler
Message board for the users of flat assembler.
 flat assembler > Examples and Tutorials > Calculation of all N! permutations
Author
SergeASM

Joined: 13 Nov 2015
Posts: 21

# Calculation of all N! permutations

I just port to FASM my function to calculate a "next" permutation. The algorithm is called a "ladder". I saw it in the book

Martin Gardner
Time Travel and Other Mathematical Bewilderments
W.H. Freeman and Company New York 1988

Let we have all permutations of 1 element (number 0):

0

To get all permutations of N+1 elements we repeat N+1 times each permutation of N elements:

0
0

Now we use the algorithm "ladder" and insert an element number N+1:
 Code: 0 1 1 0

and get all permutations of N+1 elements.

Another example:
 Code: 0 1 0 1 0 1 1 0 1 0 1 0

 Code: 0   1 2    0 2 1 2  0   1 2  1   0    1 2 0    1   0 2

Now we get all the permutations of 4 elements:

 Code: 0   1   2 3    0   1 3 2    0 3 1   2 3  0   1   2 3  0   2   1    0 3 2   1    0   2 3 1    0   2   1 3    2   0   1 3    2   0 3 1    2 3 0   1 3  2   0   1 3  2   1   0    2 3 1   0    2   1 3 0    2   1   0 3    1   2   0 3    1   2 3 0    1 3 2   0 3  1   2   0 3  1   0   2    1 3 0   2    1   0 3 2    1   0   2 3

But this algorithm is recursive, it's not good. I wrote a function Next_permutation that takes any permutation and calculates the next permutation by this algorithm!

This list of N! permutations has two great features:

1. All permutations can be arranged on a circle and each one differs from two neighbor by 1 transposition neighboring elements.
2. Calculation of first N!/2 permutations is enough, because list of the next N!/2 permutations is mirror-symmetric to the list of first N!/2 permutations! We simply reverse each of first N!/2 permutations to get other N!/2!

I've attached simple console test app. While the function is not optimized and not combed. I hope it can be used in combinatorial mathematic.

Sorry for my English

Serge

20 Nov 2015, 09:46
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------Blog General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum