permutations

*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%()) LOCAL first, last, elementcount, pos elementcount = DIM(A%(),1) IF elementcount < 1 THEN ENDPROC pos = elementcount-1 WHILE A%(pos) >= A%(pos+1) pos -= 1 IF pos < 0 THEN PROC_Permutation_Reverse(A%(), 0, elementcount) ENDPROC ENDIF ENDWHILE last = elementcount WHILE A%(last) <= A%(pos) last -= 1 ENDWHILE SWAP A%(pos), A%(last) PROC_Permutation_Reverse(A%(), pos+1, elementcount) ENDPROC DEF PROC_Permutation_Reverse(A%(), first, last) WHILE first < last SWAP A%(first), A%(last) first += 1 last -= 1 ENDWHILE ENDPROC

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

S% = 4 DIM A%(S%), O%(S%) REM Fill the array FOR I% = 0 TO S% : A%(I%) = I% : NEXT REM Set O%() to hold the original array O%() = A%() REM A one line factorial function DEF FN_Factorial(N) : IF (N = 1) OR (N = 0) THEN = 1 ELSE = N * FN_Factorial(N-1) REM Calculate the permutations N% = FN_Factorial(DIM(A%(),1)+1) C% = 0 REPEAT FOR I%= 0 TO S% PRINT ;A%(I%);" "; NEXT PROC_NextPermutation(A%()) C% += 1 PRINT UNTIL C% = N% PRINT "Number of Permutations = ";C%

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

A$ = "BB4W" N% = FN_Factorial(LEN(A$)) PRINT" There are ";N%;" permutations of ";A$ FOR I% = 1 TO N% A$ = FN_NextPermutation$(A$) PRINT I%," "A$ NEXT END DEF FN_NextPermutation$(A$) LOCAL A%(),I% DIM A%(LENA$-1) FOR I%=0 TO (LENA$-1) A%(I%) = ASCMID$(A$,I%+1) NEXT PROC_NextPermutation(A%()) FOR I%=0 TO (LENA$-1) MID$(A$,I%+1,1) = CHR$A%(I%) NEXT =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:

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

or

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

This website uses cookies. By using the website, you agree with storing cookies on your computer. Also you acknowledge that you have read and understand our Privacy Policy. If you do not agree leave the website.More information about cookies

permutations.txt · Last modified: 2018/04/17 19:12 by tbest3112

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