flat assembler
Message board for the users of flat assembler.

Index > Tutorials and Examples > Calculation of all N! permutations

Author
Thread Post new topic Reply to topic
SergeASM



Joined: 13 Nov 2015
Posts: 21
SergeASM 20 Nov 2015, 09:46
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


Description:
Download
Filename: test_permutation.zip
Filesize: 1.94 KB
Downloaded: 750 Time(s)

Post 20 Nov 2015, 09:46
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.