Task

Write a program that generates all   permutations   of   n   different objects.   (Practically numerals!)



Related tasks
 
   Find the missing permutation
   Permutations/Derangements



 The number of samples of size k from n objects.


With   combinations and permutations   generation tasks. 






 Order Unimportant

 Order Important


 Without replacement








(


n
k


)




=

n



C

k


=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}










n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




Task: Combinations

Task: Permutations


 With replacement








(



n
+
k
−
1

k


)




=

n
+
k
−
1



C

k


=



(
n
+
k
−
1
)
!


(
n
−
1
)
!
k
!





{\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



 
/* ARM assembly Raspberry PI  */
/*  program permutation.s  */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
 
sMessResult:        .asciz "Value  : @ \n"
sMessCounter:       .asciz "Permutations =  @  \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
TableNumber:       .int   1,2,3
                   .equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              @ entry of program 
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#NBELEMENTS                             @ number of élements 
    mov r10,#0                                     @ counter
    bl heapIteratif
    mov r0,r10                                     @ display counter
    ldr r1,iAdrsZoneConv                           @ 
    bl conversion10S                               @ décimal conversion 
    ldr r0,iAdrsMessCounter
    ldr r1,iAdrsZoneConv                           @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess                               @ display message
 
100:                                               @ standard end of the program 
    mov r0, #0                                     @ return code
    mov r7, #EXIT                                  @ request to exit program
    svc #0                                         @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrsMessCounter:         .int sMessCounter
/******************************************************************/
/*     permutation by heap iteratif (wikipedia)                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the eléments number  */
heapIteratif:
    push {r3-r9,lr}                @ save registers
    lsl r9,r1,#2                   @ four bytes by count
    sub sp,sp,r9
    mov fp,sp
    mov r3,#0
    mov r4,#0                      @ index
1:                                 @ init area counter
    str r4,[fp,r3,lsl #2]
    add r3,r3,#1
    cmp r3,r1
    blt 1b
 
    bl displayTable
    add r10,r10,#1
    mov r3,#0                       @ index
2:
    ldr r4,[fp,r3,lsl #2]           @ load count [i]
    cmp r4,r3                       @ compare with i
    bge 5f
    tst r3,#1                       @ even ?
    bne 3f
    ldr r5,[r0]                     @ yes load value A[0]
    ldr r6,[r0,r3,lsl #2]           @ and swap with value A[i]
    str r6,[r0]
    str r5,[r0,r3,lsl #2]
    b 4f
3:
    ldr r5,[r0,r4,lsl #2]         @ load value A[count[i]]
    ldr r6,[r0,r3,lsl #2]         @ and swap with value A[i]
    str r6,[r0,r4,lsl #2]
    str r5,[r0,r3,lsl #2]
4:
    bl displayTable
    add r10,r10,#1
    add r4,r4,#1                    @ increment count i
    str r4,[fp,r3,lsl #2]           @ and store on stack
    mov r3,#0                       @ raz index
    b 2b                            @ and loop
5:
    mov r4,#0                       @ raz count [i]
    str r4,[fp,r3,lsl #2]
    add r3,r3,#1                    @ increment index
    cmp r3,r1                       @ end ?
    blt 2b                          @ no -> loop
 
    add sp,sp,r9                    @ stack alignement
100:
    pop {r3-r9,lr}
    bx lr                           @ return 
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayTable:
    push {r0-r3,lr}                                    @ save registers
    mov r2,r0                                          @ table address
    mov r3,#0
1:                                                     @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsZoneConv                               @ 
    bl conversion10S                                    @ décimal conversion 
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv                               @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess                                   @ display message
    add r3,#1
    cmp r3,#NBELEMENTS - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
    mov r0,r2
100:
    pop {r0-r3,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 