User Tools

Site Tools


permutations

Differences

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

Link to this comparison view

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