Trace:

permutations

This shows you the differences between two versions of the page.

permutations [2018/03/31 13:19] 127.0.0.1 external edit |
permutations [2018/04/17 18:12] (current) tbest3112 Added syntax highlighting |
||
---|---|---|---|

Line 3: | Line 3: | ||

====== Permutations and Derangements ====== | ====== Permutations and Derangements ====== | ||

//by Michael Hutton May 2011//\\ \\ You may want to find all the possible permutations of a set. The following procedure(s) will take an integer array of values (they could be numbers or pointers to strings for example) and calculate the next lexicographical permutation of the array.\\ \\ | //by Michael Hutton May 2011//\\ \\ You may want to find all the possible permutations of a set. The following procedure(s) will take an integer array of values (they could be numbers or pointers to strings for example) and calculate the next lexicographical permutation of the array.\\ \\ | ||

+ | <code bb4w> | ||

DEF PROC_NextPermutation(A%()) | DEF PROC_NextPermutation(A%()) | ||

LOCAL first, last, elementcount, pos | LOCAL first, last, elementcount, pos | ||

Line 30: | Line 31: | ||

ENDWHILE | ENDWHILE | ||

ENDPROC | ENDPROC | ||

+ | </code> | ||

\\ So, for example to find all the permutations of a 5 element array:\\ | \\ So, for example to find all the permutations of a 5 element array:\\ | ||

+ | <code bb4w> | ||

S% = 4 | S% = 4 | ||

DIM A%(S%), O%(S%) | DIM A%(S%), O%(S%) | ||

Line 55: | Line 58: | ||

UNTIL C% = N% | UNTIL C% = N% | ||

PRINT "Number of Permutations = ";C% | PRINT "Number of Permutations = ";C% | ||

+ | </code> | ||

\\ or alternatively, to find all the permutations of a string use this code:\\ | \\ or alternatively, to find all the permutations of a string use this code:\\ | ||

+ | <code bb4w> | ||

A$ = "BB4W" | A$ = "BB4W" | ||

N% = FN_Factorial(LEN(A$)) | N% = FN_Factorial(LEN(A$)) | ||

Line 77: | Line 82: | ||

NEXT | NEXT | ||

=A$ | =A$ | ||

+ | </code> | ||

\\ To calculate the number of **Derangements** ie. the number of permutations in which no item appears in its original place you can calculate the SubFactorial of the number of items.\\ \\ There are two ways of doing this, either:\\ | \\ To calculate the number of **Derangements** ie. the number of permutations in which no item appears in its original place you can calculate the SubFactorial of the number of items.\\ \\ There are two ways of doing this, either:\\ | ||

+ | <code bb4w> | ||

DEF FN_SubFactorial(N) : IF N<1 THEN =1 ELSE =(N-1)*(FN_SubFactorial(N-1)+FN_SubFactorial(N-2)) | DEF FN_SubFactorial(N) : IF N<1 THEN =1 ELSE =(N-1)*(FN_SubFactorial(N-1)+FN_SubFactorial(N-2)) | ||

+ | </code> | ||

or\\ | or\\ | ||

+ | <code bb4w> | ||

DEF FN_SubFactorial(N) : IF N=0 THEN =1 ELSE = N*FN_SubFactorial(N-1)+-1^N | DEF FN_SubFactorial(N) : IF N=0 THEN =1 ELSE = N*FN_SubFactorial(N-1)+-1^N | ||

+ | </code> |

permutations.txt ยท Last modified: 2018/04/17 18:12 by tbest3112

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International