Permutation Generator by Paul Guertin
[Up to Source Code Repository]

Permutation Generator

How to generate permutations in 6502 assembly.
By Paul Guertin (pg@sff.net), 19 August 2000.

If you have n distinct elements, there are n! ways of arranging them in order. For example, the 3!=6 permutations of the digits "123" are 123, 213, 312, 132, 231, and 321.

Generating permutations is usually done with a recursive procedure, but here is a cute iterative routine that does it simply and efficiently. One caveat: permutations are not generated in lexicographical order, but in an order such that two successive permutations differ by exactly one swap (as in the list above).

To keep this routine as generic as possible, it calls two user-supplied subroutines: EXCHANGE, which swaps elements X and Y, and PROCESS, which does something with the permutation (such as print it). This way, you can easily permute any data set.

SIZE     EQU 4           ; Number of elements to permute
TEMP     EQU $6          ; (1 byte) Temporary storage

PERMGEN:
         LDA #0          ; Clear the stack
         LDX #SIZE-1
CLRSTK   STA STK,X
         DEX
         BPL CLRSTK
         BMI START       ; Do first permutation

LOOP     LDA STK,X
         STX TEMP
         CMP TEMP        ; Swap two elements if stk,x < x
         BCS NOEXCH      ; else just increment x
         INC STK,X
         TAY
         TXA
         LSR             ; Check whether x is even or odd
         BCS XODD        ;  x odd  -> swap x and stk,x
         LDY #0          ;  x even -> swap x and 0
XODD     JSR EXCHANGE    ; Swap elements x and y (user-supplied)
START    JSR PROCESS     ; Use the permutation (user-supplied)
         LDX #1          ;
         BNE LOOP        ; (always)

NOEXCH   LDA #0          ; No exchange this pass,
         STA STK,X       ; so we go up the stack
         INX
         CPX #SIZE
         BCC LOOP        ; Loop until all permutations generated
         RTS
STK      DS  SIZE        ; Stack space (ds reserves "size" bytes)

EXAMPLE  LDX #SIZE-1     ; Set up ASCII digit string
         CLC
EINIT    TXA
         ADC #"1"
         STA DIGIT,X
         DEX
         BPL EINIT
         JMP PERMGEN     ; Jump to permutation generator
DIGIT    DS  SIZE

EXCHANGE LDA DIGIT,X     ; Swap two digits in the string
         PHA
         LDA DIGIT,Y
         STA DIGIT,X
         PLA
         STA DIGIT,Y
         RTS

PROCESS  LDX #0          ; Print the digit string (Apple II specific)
PLOOP    LDA DIGIT,X
         JSR $FDED       ; Print accumulator as ASCII character
         INX
         CPX #SIZE
         BCC PLOOP
         JMP $FD8E       ; Print a carriage return