=====Permutations=====

====== 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.\\ \\ 
<code bb4w>
        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
</code>
\\  So, for example to find all the permutations of a 5 element array:\\ 
<code bb4w>
        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%
</code>
\\  or alternatively, to find all the permutations of a string use this code:\\ 
<code bb4w>
        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$
</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:\\ 
<code bb4w>
  DEF FN_SubFactorial(N) : IF N<1 THEN =1 ELSE =(N-1)*(FN_SubFactorial(N-1)+FN_SubFactorial(N-2))
</code>
or\\ 
<code bb4w>
  DEF FN_SubFactorial(N) : IF N=0 THEN =1 ELSE = N*FN_SubFactorial(N-1)+-1^N
</code>