1

Automazione dell’algoritmo ricorsivo di permutazione eseguita da Mariano Melchiorri

2

PERM(Char []A,int K)

If(k=n) Controllo (A); else {for(int =k;i<n;i++);

SWAP(A[i],A[k]); PERM(A,K+1); SWAP(A[i],A[k]);}

Dove:1. n = dimensione dell’array A 2. Controllo è la chiamata ad un metodo che visualizza le permutazioni di A3. SWAP è la chiamata ad un metodo che scambia i valori degli elementi passati

come parametro attualeNelle diapositive successive è riportato lo stato degli indici k e i all’interno di ogni chiamata durante l’esecuzione del corpo del metodo.

3

PERM(Char []A,int K)

Invocazione (1) A={a,b,c}; n=A.length=3

PERM(A,0)

codice

1)If(k=n) Controllo (A); else{

2)for(int =k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 0 a b c2 0 0 a b c3 0 0 a b c4 0 0 a b c

1° chiamata ricorsiva da (1)

Invocazione (2)2

4

PERM(Char []A,int K)

Invocazione (2) 1°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 1 a b c2 1 1 a b c3 1 1 a b c4 1 1 a b c

1° chiamata ricorsiva da (2)

Invocazione (3)

3

5

PERM(Char []A,int K)

Invocazione (3) 1°chiamata da (2)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 a b c2 2 2 a b c3 2 2 a b c4 2 2 a b c

1° chiamata ricorsiva da (3)

Invocazione (4)

4

6

PERM(Char []A,int K)

Invocazione (4) 1°chiamata da (3)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 3 a b c

Chiamata Controllo(A) e uscita con ritorno a Invocazione (3)

3

Permutazione a b c

7

PERM(Char []A,int K)

Invocazione (3) 1°chiamata da (2)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 a b c2 2 2 a b c3 2 2 a b c4 2 2 a b c5 2 2 a b c2 2 3 a b cFine primo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (2)

4

2

8

PERM(Char []A,int K)

Invocazione (2) 1°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 a b c2 1 1 a b c3 1 1 a b c4 1 1 a b c5 1 1 a b c2 1 2 a b c3 1 2 a c b4 1 2 a c b

2° chiamata ricorsiva da 2Invocazione (5)

3

5

9

PERM(Char []A,int K)

Invocazione (5) 2°chiamata da (2)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 a c b2 2 2 a c b3 2 2 a c b4 2 2 a c b

1° chiamata ricorsiva da (5)Invocazione (6)

6

10

PERM(Char []A,int K)

Invocazione (6) 1°chiamata da (5)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 3 a c b

Chiamata Controllo(A) e uscita con ritorno a Invocazione (5)

5

Permutazione a c b

11

PERM(Char []A,int K)

Invocazione (5) 2°chiamata da (2)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 a c b2 2 2 a c b3 2 2 a c b4 2 2 a c b5 2 2 a c b2 2 3 a c b

6

2

Incremento di i, uscita dal for e ritorno a Invocazione (2)

12

PERM(Char []A,int K)

Invocazione (2) 1°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 a b c

2 1 1 a b c

3 1 1 a b c

4 1 1 a b c

2 1 2 a b c

3 1 2 a c b

4 1 2 a c b

5 1 2 a b c 2 1 3 a b c

5

Fine secondo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (1)

1

13

PERM(Char []A,int K)

Invocazione (1) A={a,b,c}; n=A.length=3

PERM(A,0)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 0 a b c2 0 0 a b c3 0 0 a b c4 0 0 a b c5 0 0 a b c2 0 1 a b c3 0 1 b a c4 0 1 b a c

Fine primo ciclo for

2

2° chiamata ricorsiva da (1)Invocazione (7)

7

14

PERM(Char []A,int K)

Invocazione (7) 2°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 1 b a c2 1 1 b a c3 1 1 b a c4 1 1 b a c

1° chiamata ricorsiva da (7)

Invocazione (8)

8

15

PERM(Char []A,int K)

Invocazione (8) 1°chiamata da (7)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 b a c2 2 2 b a c3 2 2 b a c4 2 2 b a c

1° chiamata ricorsiva da (8)

Invocazione (9)

9

16

PERM(Char []A,int K)

Invocazione (9) 1°chiamata da (3)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 3 b a c

Chiamata Controllo(A) e uscita con ritorno a Invocazione (8)

8

Permutazione b a c

17

PERM(Char []A,int K)

Invocazione (8) 1°chiamata da (7)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 b a c2 2 2 b a c3 2 2 b a c4 2 2 b a c5 2 2 b a c2 2 3 b a cFine primo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (7)

9

7

18

PERM(Char []A,int K)

Invocazione (7) 2°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 b a c2 1 1 b a c3 1 1 b a c4 1 1 b a c2 1 2 b a c3 1 2 b c a4 1 2 b c a2° chiamata ricorsiva da (7)

Invocazione (10)

8

10

19

PERM(Char []A,int K)

Invocazione (10) 2°chiamata da (7)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 b c a2 2 2 b c a3 2 2 b c a4 2 2 b c a

1° chiamata ricorsiva da (10)Invocazione (11)

11

20

PERM(Char []A,int K)

Invocazione (11) 1°chiamata da (10)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 3 b c a

Chiamata Controllo(A) e uscita con ritorno a Invocazione (10)

10

Permutazione b c a

21

PERM(Char []A,int K)

Invocazione (10) 2°chiamata da (7)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 b c a2 2 2 b c a3 2 2 b c a4 2 2 b c a5 2 2 b c a2 2 3 b c a

11

7Incremento di i, uscita dal for e ritorno a Invocazione (7)

22

PERM(Char []A,int K)

Invocazione (7) 2°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 b a c

2 1 1 b a c

3 1 1 b a c

4 1 1 b a c

2 1 2 b a c

3 1 2 b c a

4 1 2 b c a

5 1 2 b a c 2 1 3 b a c

10

Fine secondo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (1)

1

23

PERM(Char []A,int K)

Invocazione (1) A={a,b,c}; n=A.length=3

PERM(A,0)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 0 a b c

2 0 0 a b c

3 0 0 a b c

4 0 0 a b c

5 0 0 a b c

2 0 1 a b c

3 0 1 b a c

4 0 1 b a c

5 0 1 a b c

2 0 2 a b c

3 0 2 c b a

4 0 2 c b a

Fine secondo ciclo for

7

3° chiamata ricorsiva da (1)Invocazione (12) 12

24

PERM(Char []A,int K)

Invocazione (12) 3°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 1 c b a2 1 1 c b a3 1 1 c b a4 1 1 c b a

1° chiamata ricorsiva da (12)

Invocazione (13)

13

25

PERM(Char []A,int K)

Invocazione (13) 1°chiamata da (12)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 c b a2 2 2 c b a3 2 2 c b a4 2 2 c b a

1° chiamata ricorsiva da (13)

Invocazione (14)

14

26

PERM(Char []A,int K)

Invocazione (14) 1°chiamata da (13)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 3 c b a

Chiamata Controllo(A) e uscita con ritorno a Invocazione (13)

13

Permutazione c b a

27

PERM(Char []A,int K)

Invocazione (13) 1°chiamata da (12)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr. k i A

1 2 c b a2 2 2 c b a3 2 2 c b a4 2 2 c b a5 2 2 c b a2 2 3 c b aFine primo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (12)

14

12

28

PERM(Char []A,int K)

Invocazione (12) 3°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 c b a2 1 1 c b a3 1 1 c b a4 1 1 c b a5 1 1 c b a2 1 2 c b a3 1 2 c a b4 1 2 c a b

2° chiamata ricorsiva da (12)Invocazione (15)

13

15

29

PERM(Char []A,int K)

Invocazione (15) 2°chiamata da (12)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 c a b2 2 2 c a b3 2 2 c a b4 2 2 c a b

1° chiamata ricorsiva da (15)Invocazione (16)

16

30

PERM(Char []A,int K)

Invocazione (16) 1°chiamata da (15)

PERM(A,3)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 3 c a b

Chiamata Controllo(A) e uscita con ritorno a Invocazione (15)

15

Permutazione c a b

31

PERM(Char []A,int K)

Invocazione (15) 2°chiamata da (12)

PERM(A,2)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 2 c a b2 2 2 c a b3 2 2 c a b4 2 2 c a b5 2 2 c a b2 2 2 c a b

16

12

Incremento di i, uscita dal for e ritorno a Invocazione (12)

32

PERM(Char []A,int K)

Invocazione (12) 3°chiamata da (1)

PERM(A,1)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++){

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}}

Istr. k i A

1 1 c b a

2 1 1 c b a

3 1 1 c b a

4 1 1 c b a

2 1 2 c b a

3 1 2 c a b

4 1 2 c a b

5 1 2 c b a2 1 3 c b a

15

Fine secondo ciclo di for

Incremento di i, uscita dal for e ritorno a Invocazione (1)

1

33

PERM(Char []A,int K)

Invocazione (1) A={a,b,c}; n=A.length=3

PERM(A,0)

codice

1)If(k=n) Controllo (A); else{

2)for(int i=k;i<n;i++);

3)SWAP(A[i],A[k]);

4)PERM(A,K+1);

5)SWAP(A[i],A[k]);}

Istr.

k i A

1 0 a b c

2 0 0 a b c

3 0 0 a b c

4 0 0 a b c

5 0 0 a b c

2 0 1 a b c

3 0 1 b a c

4 0 1 b a c

5 0 1 a b c

2 0 2 a b c

3 0 2 c b a

4 0 2 c b a

5 0 2 a b c

2 0 3

Fine terzo ciclo for

12Fine esecuzione