permutations

# Differences

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 2018/04/17 18:12 tbest3112 Added syntax highlighting2018/03/31 13:19 external edit 2018/04/17 18:12 tbest3112 Added syntax highlighting2018/03/31 13:19 external edit 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.\\ \\ + 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 + ​ \\  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:​\\ ​ + 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% + ​ \\  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:​\\ ​ + A\$ = "​BB4W"​ A\$ = "​BB4W"​ 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:​\\ ​ + 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\\ + 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 +   ​ 