permutations
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| permutations [2018/03/31 13:19] – external edit 127.0.0.1 | permutations [2024/01/05 00:21] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| 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, | LOCAL first, last, elementcount, | ||
| Line 30: | Line 31: | ||
| ENDWHILE | ENDWHILE | ||
| ENDPROC | ENDPROC | ||
| + | </ | ||
| \\ 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 " | PRINT " | ||
| + | </ | ||
| \\ or alternatively, | \\ or alternatively, | ||
| + | <code bb4w> | ||
| A$ = " | A$ = " | ||
| N% = FN_Factorial(LEN(A$)) | N% = FN_Factorial(LEN(A$)) | ||
| Line 77: | Line 82: | ||
| NEXT | NEXT | ||
| =A$ | =A$ | ||
| + | </ | ||
| \\ 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)) | ||
| + | </ | ||
| 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 | ||
| + | </ | ||
permutations.1522502373.txt.gz · Last modified: 2024/01/05 00:17 (external edit)