[Return to Main Page]

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 of use:
print all permutations of integers {1, 2, ..., SIZE}

    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

Here are the two sub-routines:

    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

Last page update: August 19, 1999.