I'm trying to list all the permutations of the first N natural numbers (N <= 6) with MSVC Assembly 8086 inline. I can't change anything of the C program, I can only manage the assembly code. So this is what I've done (and works with N <= 3), using the lexicographic algorithm:
#include <stdio.h>
int main() {
// Variabili
int N=4; // N <= 6
int Perm[4326]; // permutations array: the dimension is sufficient for N <= 6
int Num; // At the end it must contains the number of generated permutations
// Assembler block
__asm
{
XOR EAX, EAX ; Reset EAX (permutations counter)
MOV ECX, N ; Put N into ECX
CMP ECX, 1 ; Compare ECX and 1
JBE Piccolo ; If ECX <= 1 go to Piccolo (particular cases 1 and 0)
DEC ECX ; Decrement ECX (so ECX = N - 1)
MOV EAX, N ; Put N into EAX
MaxPerm:
MUL ECX ; Do EDX:EAX = EAX * ECX
LOOP MaxPerm ; Loop to find permutations number
MOV Num, EAX ; Move EAX (permutations number) into Num
MOV EAX, 1 ; Set EAX (permutations number) to 1
MOV EBX, 0 ; Reset EBX (EBX = 0)
MOV ECX, 1 ; Reset ECX
CicloIniziale:
DEC ECX ; Decrement ECX (to compare it with N)
CMP ECX, N ; Compare ECX and N
JE Permutazione ; If ECX == N the first permutation has been written, skip to the generation of the next ones
INC ECX ; Else increment ECX
MOV Perm[4*EBX], ECX ; Insert ECX into the Perm array
INC ECX ; Increment ECX
INC EBX ; Increment EBX
JMP CicloIniziale ; Continue the loop
Permutazione:
XOR EAX, EAX ; Local index
XOR EBX, EBX ; Previous permutation index
MOV ECX, N ; Current permutation index
MOV EDI, 1 ; Value of k
MOV ESI, 1 ; New position of k
CicloPermutazione:
CMP EAX, N ; Compare ECX and EAX
JE ResetPerm ; If the end of the permutation has been reached, go to ResetPerm
MOV EDX, Perm[4*EBX] ; Otherwise save the element of the previous permutation in position EBX in EDX
CMP EDX, EDI ; Compare EDX and EDI
JE ValoreUguale ; If they are equal, then go to ValoreUguale
CMP EAX, ESI ; Otherwise compare EBX and ESI
JE InserisciElSpostato ; If it's time to move the item, go to InserisciElSpostato
MOV Perm[4*ECX], EDX ; Returns the value of the previous permutation to the new permutation
ContinuaCiclo:
INC EBX ; Increment the previous permutation index
INC EAX ; Increment the local index
INC ECX ; Increment the new permutation index
JMP CicloPermutazione ; Continue the loop
InserisciElSpostato:
MOV Perm[4*ECX], EDI ; Put EDI in the new permutation
MOV EDX, N ; EDX = N
DEC EDX ; EDX -= 1
CMP ESI, EDX ; Compare ESI and EDX
JE ResettaK ; If ESI == EDX go to ResettaK
JMP ContinuaCiclo ; Continue the loop
ValoreUguale:
CMP EAX, 0 ; Confronta EAX e 0
JZ PrimaPos ; If EAX == 0 (first position) go to PrimaPos
MOV EDX, Perm[4*EBX+4] ; Else save the element into position EBX - 1
MOV Perm[4*ECX], EDX ; Insert EDX in the new permutation
JMP ContinuaCiclo ; Continue the loop
PrimaPos:
MOV EDX, Perm[4*EBX+4] ; Save into EDX the element in position ECX + 1
MOV Perm[4*ECX], EDX ; Insert EDX into the new permutation
JMP ContinuaCiclo ; Continue the loop
ResettaK:
XOR ESI, ESI ; Reset ESI
MOV EDI, Perm[4*EDI] ; EDI = Perm[EDI]
JMP ContinuaCiclo ; Continue the loop
ResettaKN:
CMP EDI, N ; Compare EDI and N
JNE ContinuaCiclo ; if EDI != N then continue the loop
JMP ResettaK ; Else go to ResettaK
ResetPerm:
MOV EAX, Num ; EAX = Num
MUL DWORD PTR N ; EAX *= N (Elements of number of all the permutations)
CMP EAX, ECX ; Compare EAX and ECX
JE Fine ; If EAX == ECX (permutations done) then finish the program
XOR EAX, EAX ; Otherwise reset EAX
INC ESI ; Increment k index
JMP CicloPermutazione ; Continue the loop
Piccolo: ; If N = 0 or N = 1, the only permutation that can exists is made by only 1 element
MOV Num, 1
MOV Perm[0], ECX
Fine:
}
// Print
{
int i,j,k;
printf("%d permutations of the first %d natural numbers\n", Num, N);
for (i=k=0;i<Num;i++)
{
for (j=0;j<N;j++)
{
printf("%3d",Perm[k++]);
}
printf("\n");
}
}
return 0;
}
The issue is that this program works only for N <= 3 and I didn't found the issue! These are the outputs I get:
N = 3 and below works fine:
6 permutations of the first 3 natural numbers
1 2 3
2 1 3
2 3 1
3 2 1
3 1 2
1 3 2
N = 4 (the same with 5 and 6):
24 permutations of the first 4 natural numbers
1 2 3 4
2 1 3 4
2 3 1 4
2 3 4 1
3 2 4 1
3 4 2 1
3 4 1 2
4 3 1 2
4 1 3 2
4 1 2 3
1 4 2 3
1 2 4 3
1 2 3 4
1 3 3 4
1 3 2 4
1 3 4 2
1 4 4 2
1 4 3 2
1 4 2 3
1 2 2 3
1 2 4 3
1 2 3 4
1 3 3 4
1 3 2 4
As you can see after the last permutation of the first cycle the next ones are messed up...
Can you help me? Thanks
In the end, I've managed to write a C program that does the job using the algorithm fo the next_permutation function of the C++ STD lib. Then, I've translated the C code into assembly with the help of Godbolt (online compiler).
So:
next_permutation function: https://godbolt.org/z/7avGaWfha