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:
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 SIZEHere 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 returnLast page update: August 19, 1999.