flat assembler
Message board for the users of flat assembler.
Index
> Tutorials and Examples > Calculation of all N! permutations |
Author |
|
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
|
|||||||||||
20 Nov 2015, 09:46 |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.