Thursday, July 06, 2017

Algoritmo per l'estrazione di n numeri casuali


Questo post nasce a seguito di una breve discussione intercorsa con il mio caro amico Mario Monfrecola che mi chiedeva, a titolo d'esercizio, di trovare un algoritmo per la generazione di n numeri casuali interi distinti, tutti compresi nell'intervallo [1, n].
La soluzione che ho immaginato è quella che vado a descrivere nel seguito e che ho pensato, avendo sempre a mente un uso parsimonioso della memoria, di realizzare utilizzando un unico array, di lunghezza n, che alla fine dell'elaborazione conterrà la sequenza dei numeri estratti.
Innanzitutto, viene inizializzato un array con la successione di tutti i numeri da 1 a n.
Poi, viene eseguito un ciclo di n passi in cui, ad ogni passo p, viene generato un numero casuale intero compreso tra 1 e n - p + 1, l'elemento dell'array che si trova in corrispondenza di tale numero viene aggiunto in coda all'array e poi dallo stesso array viene rimosso l'elemento che si trova nella posizione del numero casuale generato.
Per chiarire meglio quanto detto, vediamo un esempio concreto in cui, per semplicità, consideriamo il caso n = 5.
Allora, inizialmente l'array viene inizializzato nel seguente modo:
[1, 2, 3, 4, 5]

Passo 1
Il numero estratto ha un valore compreso tra 1 e 5.
Supponiamo che tale valore sia 5.
Allora il numero che si trova in posizione 5 viene aggiunto in coda all'array: [1, 2, 3, 4, 5, 5] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso resta invariato:
[1, 2, 3, 4, 5]

Passo 2
Il numero estratto ha un valore compreso tra 1 e 4.
Supponiamo che tale valore sia 1.
Allora il numero che si trova in posizione 1 viene aggiunto in coda all'array: [1, 2, 3, 4, 5, 1] e dall'array viene rimosso l'elemento che si trova in prima posizione; per cui esso diventa:
[2, 3, 4, 5, 1]

Passo 3
Il numero estratto ha un valore compreso tra 1 e 3.
Supponiamo che tale valore sia 2.
Allora il numero che si trova in posizione 2 viene aggiunto in coda all'array: [2, 3, 4, 5, 1, 3] e dall'array viene rimosso l'elemento che si trova in seconda posizione; per cui esso diventa:
[2, 4, 5, 1, 3]

Passo 4
Il numero estratto ha un valore compreso tra 1 e 2.
Supponiamo che tale valore sia 2.
Allora il numero che si trova in posizione 2 viene aggiunto in coda all'array: [2, 4, 5, 1, 3, 4] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso diventa:
[2, 5, 1, 3, 4]

Passo 5
Il numero estratto ha un valore compreso tra 1 e 1.
Quindi, all'ultimo passo, tale valore è necessariamente 1.
Allora il numero che si trova in posizione 1 viene aggiunto in coda all'array: [2, 5, 1, 3, 4, 2] e dall'array viene rimosso l'elemento che si trova in quinta posizione; per cui esso diventa:
[5, 1, 3, 4, 2]

Da quanto visto, ci rendiamo anche conto del fatto che l'ultimo passo può essere evitato in quanto il numero generato non è casuale ma vale sempre 1 e ha il solo effetto di spostare il primo elemento dell'array in coda allo stesso ma poiché per noi non è importante la sua posizione, possiamo anche saltare tale passo limitando il ciclo fino al passo n-1; per cui, nel caso visto sopra, l'array dell'estrazione sarà quello del passo 4: [2, 5, 1, 3, 4].

Come visto, l'algoritmo è estremamente semplice e la sua implementazione in un linguaggio di programmazione ad alto livello è pressoché immediata.
A titolo d'esempio, ne propongo una in Java:

// Impostare n con un opportuno valore
final int n = 90;
ArrayList a = new ArrayList(n + 1);
Random random = new Random();
for (int i = 0; i < n; i++)
a.add(i, i + 1);
for (int i = 0; i < n - 1; i++) {
int j = random.nextInt(n - i) + 1;
a.add(a.get(j - 1));
a.remove(j - 1);
}
System.out.println(a);

Monday, May 13, 2013

Commodore 64: Ritorno alle origini!


Se qualcuno mi chiedesse qual è il computer che ha maggiormente segnato l'home computing in Italia, non esiterei a rispondere: il Commodore 64!
A metà degli anni ottanta, macchine come il Vic 20 ed il Commodore 64 erano le protagoniste indiscusse del panorama informatico italiano di quegli anni.
Anzi, per dirla tutta, il Commodore 64 non veniva considerato come UN computer ma come IL computer (con buona pace per tutti i fan Sinclair!), più vicino ad un oggetto di cult che ad una semplice macchina. Inoltre, dato l'enorme successo riscosso, fiorivano riviste mitiche quali: Superfloppy 64, Commodore Computer Club, Commodore Gazzette, Bit, MC Micro Computer, Papersoft e tante altre.
Insomma la Commodore ha scritto la storia dell'informatica in Italia (e, forse, nel mondo), facendo appassionare all'informatica tantissime persone, contribuendo anche a realizzare il sogno di Bill Gates: un computer in ogni casa.
Oggi, ad oltre trent'anni di distanza, il ricordo di quel periodo è sempre vivo in chi, come il sottoscritto, lo ha vissuto.
Me ne rendo conto navigando su internet dove è possibile scaricare in modo gratuito tanti emulatori del Commodore 64 e moltissimo software ad esso dedicato.
Ancora oggi ci sono tantissimi appassionati che si dilettano a realizzare programmi per questo meraviglioso computer.
Un'ottima testimonianza è costituita dall'intervento del bravo Giovanni Simotti che, al codemotion 2012, ha efficacemente illustrato come ancora oggi, ad oltre trent'anni dalla sua nascita, sia possibile programmare il Commodore 64 con strumenti moderni.
Così anch'io mi sono detto: perchè non riprovarci? Ed allora, di buona lena, ho deciso di mettermi all'opera ed ho deciso di scrivere un'implementazione dell'algoritmo per lo sviluppo di sistemi integrali del totocalcio, presentato nel primo topic di questo blog.
La prima cosa che ho fatto è stata quella di procurarmi un buon emulatore.
La scelta è caduta sull'ottimo VICE che, oltre ad emulare diversi tipi di macchina di casa Commodore, dispone anche di un ottimo debbugger le cui modalità di utilizzo sono descritte abbastanza bene su questo link.
La seconda è stata quella di procurarmi un buon IDE che semplificasse la scrittura del programma da eseguire con l'emulatore.
La scelta è caduta sull'ottimo CBM .prg Studio di Arthur Jordison che permette di scrivere in modo ottimale programmi per vari tipi di computer di casa Commodore quali: VIC 20, Commodore 64, Commodore 128, Commodore 16, Plus/4 e Pet.
Una volta avuti a disposizione tali strumenti di sviluppo, ho provveduto a scrivere una prima stesura in basic dell'algoritmo che desideravo implementare.
Il codice che ho sviluppato è il seguente:

10 input"{clear}quante parite";n
20 if n<1 or n>16 then 10
30 dim bs(n): cs=1: pr$="": print: for i=1 to n
40 print"partita n.";i;"{left}";: input p$
50 cs=cs*len(p$): bs(i)=len(p$): pr$=pr$+p$
60 next: print: print"{down}colonne da sviluppare:"; cs
70 print: for i=1 to cs: gosub 80: print cl$: next: end
80 cl$="": pt=len(pr$)-bs(n): nc=i-1: for j=n to 1 step -1
90 cl$=mid$(pr$, nc-int(nc/bs(j))*bs(j)+pt+1, 1)+cl$
100 nc=int(nc/bs(j)):if j>1 then pt=pt-bs(j-1)
110 next: return

Tale programma, sebbene sia di dimensioni molto ridotte ed eseguibile praticamente su tutte le macchine di casa Commodore, ha il difetto di non essere facilmente "traducibile" in assembler.
Il motivo di tale difficoltà deriva dal fatto che non è semplice eseguire un conteggio per numeri maggiori di 255 su macchine a 8bit.
Per tale motivo, per ovviare a tale difficoltà, ho riscritto il programma in modo tale che il conteggio non sia più eseguito con un ciclo ma mediante operazioni più "semplici".
Per fare ciò, mi sono "ispirato" ad un contatore eseguito su una macchina di Turing. Chiunque voglia vedere come questo funzioni su una tale macchina, può visitare il sito, oppure scaricare il simulatore dal sito.
Il nuovo codice sviluppato, di cui lascio ai volenterosi il compito di capirne i dettagli implementativi, è il seguente:

10 input"{clear}quante parite";n
20 if n<1 or n>16 then 10
30 dim a(n), bs(n): cs=1: pr$="": print: for i=1 to n
40 print"partita n.";i;"{left}";: input p$
50 cs=cs*len(p$): bs(i)=len(p$): pr$=pr$+p$
60 next: print: print"{down}colonne da sviluppare:"; cs
70 ps=n: dr=0: print: for i=1 to n: a(i)=0: next
80 gosub 170
90 a(ps)=a(ps)+1
100 if a(ps)
110 dr=1
120 ps=ps-1: if ps>0 then a(ps)=a(ps)+1
130 if ps>0 and a(ps)=bs(ps) and dr=1 then 120
140 if a(1)=bs(1) then end
150 for i=ps+1 to n: a(i)=0: next
160 ps=n: dr=0: goto 100
170 pt=0: for i=1 to n: print mid$(pr$, a(i)+pt+1, 1);: pt=pt+bs(i): next
180 print: return

A questo punto, mi proposi di "tradurre" tale programma in assembler, ma desideravo che il codice che sarei andato a realizzare fosse multipiattaforma; ossia che potesse essere eseguito non solo su Commodore 64 ma anche su altre macchine quali: Vic 20, Commodore 128, Commodore 16 e Plus4.
Per fare ciò, ho fatto largo utilizzo dell'indirizzamento indiretto indicizzato basandolo sulle locazioni 251($FB) e 252($FC) di pagina zero. La scelta è caduta su di esse in quanto le locazioni da 251 a 254 in pagina zero sono libere su tutte le macchine cbm.
Inoltre, ho dovuto rinunciare all'utilizzo dell'istruzione JMP basando i salti all'interno del codice sulle istruzioni CLC e BCC.
Ho cercato di eseguire la "traduzione" in assembler, per quanto possibile, riga per riga e commentando il codice indicando anche l'inizio della corrispettiva riga in basic (relativa al codice precedente).
Il codice che ho scritto, che anche in questo caso lascio ai volenterosi il compito di capirne i dettagli implementativi, è il seguente:

; Tot16

*=$C000

start  LDY #$0
       LDA ($FB),Y
       TAY
       LDA #$0
loop1  STA ($FB),Y
       DEY
       BNE loop1
       LDA ($FB),Y
       TAY         ; y=n
       LDX #$0     ; x=0
cllprt JSR subprt  ; Chiama la subroutine per stampare la colonna   ** Riga 80 **
       CLC
       LDA ($FB),Y ; a(y)=a(y)+1
       ADC #$1
       STA ($FB),Y
loop2  PHA         ; tmp=a(y)
       TYA         ; y=y+n
       CLC
       LDY #$0
       ADC ($FB),Y
       TAY
       PLA         ; a=tmp
       CMP ($FB),Y ; if a(y)==b(y) || x==1 then chgdr   ** Riga 100 **
       BEQ chgdr
       CPX #$1
       BEQ chgdr
       PHA         ; tmp=a
       TYA         ; y=y-n
       SEC
       LDY #$0
       SBC ($FB),Y
       TAY
       PLA         ; a=tmp
       CLC         ; JMP cllprt
       BCC cllprt
chgdr  LDX #$1     ; x=1     ** Riga 110 **
       PHA         ; tmp=a
       TYA         ; y=y-n
       SEC
       LDY #$0
       SBC ($FB),Y
       TAY
       PLA         ; a=tmp
loop3  DEY         ; y--     ** Riga 120 **
       CPY #$0
       BEQ chkend
       CLC         ;         ** Riga 130 **
       LDA ($FB),Y ; a=a(y)+1
       ADC #$1
       STA ($FB),Y
       PHA         ; tmp=a
       TYA         ; y=y+n
       LDY #$0
       ADC ($FB),Y
       TAY
       PLA         ; a=tmp
       CMP ($FB),Y ; if a!=b(y)
       BNE chkend
       CPX #$1
       BNE chkend
       PHA         ; tmp=a
       TYA         ; y=y-n
       LDY #$0
       SEC
       SBC ($FB),Y
       TAY
       PLA         ; a=tmp
       CLC         ; JMP loop3
       BCC loop3
jmplp2 CLC         ; JMP loop2
       BCC loop2
chkend TYA         ; y=y-n   ** Riga 140 **
       LDY #$0
       SEC
       SBC ($FB),Y
       TAY         ; y=a
       PHA         ; tmp=a
       LDY #$0
       LDA ($FB),Y
       TAY
       INY
       LDA ($FB),Y ; a=b[1]
       LDY #$1
       CMP ($FB),Y
       BEQ end
       PLA         ; a=tmp
       TAY
loop4  INY         ; ** Riga 150 **
       TYA         ; a=y
       PHA         ; tmp=a
       LDA #$0
       STA ($FB),Y
       PLA         ; a=tmp
       LDY #$0
       CMP ($FB),Y
       BEQ endres
       TAY         ; y=a
       CLC         ; JMP loop4
       BCC loop4
endres LDX #$0     ; ** Riga 160 **
       TXA
       TAY
       LDA ($FB),Y
       TAY
       LDA ($FB),Y ; a=a[n]
       CLC         ; JMP loop2: è necessario un salto più "piccolo" a jmpl2
       BCC jmplp2
end    PLA          ; Svuota lo stack
       RTS
; Subroutine per stampare la colonna
subprt PHA         ; Salva l'accumulatore nello stack
       TXA
       PHA         ; Salva il registro x nello stack
       TYA
       PHA         ; Salva il registro y nello stack
       LDX #$0     ; x=0
       LDY #$0     ; y=0
       TYA         ; tmp=y
       PHA
loop5  PLA         ; y=tmp
       TAY
       INY         ; y=y+1
       TYA         ; tmp=y
       PHA
       TXA         ; a=x+a(y)+1+n*2
       CLC
       ADC ($FB),Y
       ADC #$1
       LDY #$0
       ADC ($FB),Y
       ADC ($FB),Y
       TAY         ; y=a
       LDA ($FB),Y ; stampa il carattere
       JSR $FFD2
       PLA         ; a=y(originario corrispondente allo i-esimo)
       PHA
       LDY #$0     ; x=x+a(y+n)
       ADC ($FB),Y
       TAY       
       LDA ($FB),Y
loop6  INX
       SEC
       SBC #$1
       BNE loop6
       LDY #$0     ; Compara l'y originario con n
       PLA
       PHA
       CMP ($FB),Y
       BNE loop5   ; Se non coincide continua con la stampa
       LDA #$D
       JSR $FFD2
       PLA         ; Svuota lo stack
       PLA         ; Recupera il registro y dallo stack
       TAY
       PLA         ; Recupera il registro x dallo stack
       TAX
       PLA         ; Recupera l'accumulatore dallo stack
       RTS         ; Esce dalla subroutine

Una volta scritto tale codice, restava da scriverne il loader che si occupasse di caricarlo in memoria, rilocandolo a seconda della macchina su cui viene eseguito.
Gli unici due problemi da risolvere erano i seguenti: individuare il tipo di macchina in cui il codice viene eseguito e determinare la posizione dove allocare il programma assembler nella memoria di tale macchina.
In merito al primo problema, su internet ho trovato la seguente discussione da cui ho estratto lo snippet che ho utilizzato nel mio codice.
Per quanto riguarda il secondo, invece, ho pensato di allocare il codice 2k dopo l'inizio dell'area dedicata ad ospitare il codice basic che su tutte le macchine cbm può essere individuata grazie alle locazioni 43 e 44.
Per il Commodore 64, sebbene non necessario, ho preferito scegliere in modo deterministico l'area di memoria che inizia all'indirizzo 49152($C000).
Infine, faccio esplicitamente osservare che, limitatamente alla sola istruzione "JSR subprt", si è reso necessario modificare 2 byte del codice assembler in funzione dell'indirizzo di memoria determinato per l'inizio del programma.
Il codice che ho scritto per fare ciò è il seguente:

10 cbm=peek(65534)
20 if peek(1177)=63 then poke1177,62: cbm=peek(65534): poke1177,63
30 if cbm=72 or cbm=114 or cbm=23 or cbm=179 then 50
40 print "solo per: c64, vic20, c128, c16, plus4": end
50 if cbm=72 then sa=49152: goto 70
60 sa=peek(44)*256+peek(43)+1024*2
70 o=235: for i=0 to o-1: read a: poke sa+i,a: next
80 input"{clear}quante parite";n
90 if n<1 or n>16 then 80
100 poke sa+o,n: cs=1: pr$="": print
110 for i=1 to n
120 print"partita n.";i;"{left}";: input p$
130 cs=cs*len(p$): poke sa+o+n+i,len(p$): pr$=pr$+p$
140 next: print: print"{down}colonne da sviluppare:"; cs
150 for i=1 to len(pr$): poke sa+o+n*2+i,asc(mid$(pr$, i, 1)): next
160 hi=int((sa+o)/256): lo=(sa+o)-hi*256: poke 251,lo: poke 252,hi
170 rem modifica nel codice l'indirizzo della chiamata a subprt
180 hi=int((sa+166)/256): lo=(sa+166)-hi*256: poke sa+18,lo: poke sa+19,hi
190 sys sa
200 end
210 data 160,0,177,251,168,169,0,145
220 data 251,136,208,251,177,251,168,162
230 data 0,32,166,192,24,177,251,105
240 data 1,145,251,72,152,24,160,0
250 data 113,251,168,104,209,251,240,16
260 data 228,1,240,12,72,152,56,160
270 data 0,241,251,168,104,24,144,217
280 data 162,1,72,152,56,160,0,241
290 data 251,168,104,136,192,0,240,38
300 data 24,177,251,105,1,145,251,72
310 data 152,160,0,113,251,168,104,209
320 data 251,208,19,224,1,208,15,72
330 data 152,160,0,56,241,251,168,104
340 data 24,144,216,24,144,173,152,160
350 data 0,56,241,251,168,72,160,0
360 data 177,251,168,200,177,251,160,1
370 data 209,251,240,32,104,168,200,152
380 data 72,169,0,145,251,104,160,0
390 data 209,251,240,4,168,24,144,238
400 data 162,0,138,168,177,251,168,177
410 data 251,24,144,199,104,96,72,138
420 data 72,152,72,162,0,160,0,152
430 data 72,104,168,200,152,72,138,24
440 data 113,251,105,1,160,0,113,251
450 data 113,251,168,177,251,32,210,255
460 data 104,72,160,0,113,251,168,177
470 data 251,232,56,233,1,208,250,160
480 data 0,104,72,209,251,208,210,169
490 data 13,32,210,255,104,104,168,104
500 data 170,104,96

Tale codice ha il notevole pregio di poter essere eseguito senza alcuna modifica su molte macchine di casa Commodore.
Che altro dire?
Anche a distanza di anni il Commodore 64 continua ad affascinare ed interessare tanti suoi fan, per cui non mi resta che augurare buona programmazione a tutti coloro che vorranno cimentarsi ancora una volta a realizzare programmi per quella che è stata, e resta, una macchina mitica!

Tuesday, November 06, 2012

Algoritmo per il calcolo diretto di combinazioni


Come già detto nel precedente topic, le combinazioni, al pari delle permutazioni, rivestono un ruolo di primo piano nello sviluppo di molti software in quanto costituiscono la base di numerosi algoritmi.
Per tale motivo, in questo articolo descriveremo, come già fatto per le permutazioni, un metodo per il calcolo diretto di una specifica combinazione a partire dalla sua posizione nella lista delle combinazioni ordinate in modo lessicografico (ordine da dizionario).
Anche le combinazioni, analogamente alle permutazioni, possono essere costituite da elementi appartenenti agli insiemi più vari. Anche in questo caso, nel seguito, senza perdere di generalità, ci riferiremo a combinazioni i cui elementi sono numeri interi e, per comodità, ci riferiremo ad un caso specifico, fermo restando la validità del metodo nel caso generale.
Precisiamo, altresì, che nel seguito ci occuperemo esclusivamente delle combinazioni senza ripetizioni.
Allo scopo, ci riferiremo al caso delle combinazioni di 5 elementi presi 3 alla volta; ossia al caso n=5, k=3, in cui le combinazioni generate sono 10 e sono le seguenti:

0: [0, 1, 2]
1: [0, 1, 3]
2: [0, 1, 4]
3: [0, 2, 3]
4: [0, 2, 4]
5: [0, 3, 4]
6: [1, 2, 3]
7: [1, 2, 4]
8: [1, 3, 4]
9: [2, 3, 4]

In modo simile a quanto visto per le permutazioni, un ruolo fondamentale in tale algoritmo è svolto dal combinadic (detto anche sistema di numero combinatorio) di grado k; ossia un numero che mappa ogni indice in una nuova rappresentazione. Tale rappresentazione può essere calcolata individuando $c_1, c_2, ... c_k$ tale che ci è il più grande intero tale che $ci \choose i$<=index(i) dove index(k-1)=n-1, index(k-2)=index(k-1)-$c_{k-1} \choose k-2$, $\cdots$, index(1)=index(2)-$c_2 \choose 1$. Vediamo un esempio considerando il caso in esame e scegliendo index=4.

Il più grande intero $c_3$ tale che $c_3 \choose 3$<=4 è 4, il più grande intero $c_2$ tale che $c2 \choose 2$<=4-$4 \choose 3$=0 è 1, il più grande intero tale che $c_1 \choose 1$<=0 è 0; per cui si ha che per n=5, k=3 e index=4 il combinadic è [4, 1, 0].
Per il caso in esame, quindi, effettuando i calcoli per tutti gli indici compresi tra 0 e 9, otteniamo che la lista dei combinadic risulta essere la seguente:

0: [2, 1, 0]
1: [3, 1, 0]
2: [3, 2, 0]
3: [3, 2, 1]
4: [4, 1, 0]
5: [4, 2, 0]
6: [4, 2, 1]
7: [4, 3, 0]
8: [4, 3, 1]
9: [4, 3, 2]

Per vedere il legame tra il combinadic di un indice con la corrispondente combinazione, introduciamo il concetto di duale dell'indice che possiamo definire nel seguente modo:

dualIndex = $n \choose k$ - 1 - index

Per determinare la combinazione associata ad un dato indice, quindi, andiamo a considerare il combinadic del duale dell'indice e, detto ci il generico elemento del combinadic, poniamo:

$c_i$ = n-1-$c_i$ $\forall$ i=0,$\cdots$,k

Nel nostro caso, quindi, abbiamo che il duale dell'indice 4 è uguale a: 10-1-4 = 5 il cui combinadic è [4, 2, 0]. Da ciò segue che la combinazione associata è: [0, 2, 4].

Analogamente al caso delle permutazioni, l'algoritmo esposto è invertibile; ossia, a partire da una determinata combinazione è possibile calcolare il relativo combinadic e l'indice della combinazione. A differenza del caso precedente, però, per risalire all'indice della combinazione non è necessario calcolare necessariamente il combinadic; anzi, si può fare proprio l'inverso; ossia calcolare l'indice associato alla combinazione e da questi risalire al combinadic.
Lo snippet che consente di calcolare l'indice associato ad una determinata combinazione è il seguente:

int index = 0;
int j = 0;
for (int i = 0; i != k; ++i)
    for (++j; j != combination[i]; ++j)
        index += choose(n - j, k - i - 1);   // assume che ci sia una funzione choose(n, k) che restituisce il numero di combinazioni di n elementi presi a k la volta.

Anche questo algoritmo, come quello mostrato per le permutazioni, ha il notevole pregio di consentire l'immediata realizzazione di programmi paralleli per il calcolo di combinazioni.
Per il futuro, anche per esso, mi riservo di pubblicarne sul mio sito il codice sogente di un'implementazione Java.



Riferimenti Web:

http://msdn.microsoft.com/en-us/library/aa289166(v=vs.71).aspx

http://msdn.microsoft.com/en-us/magazine/cc163957.aspx

http://stackoverflow.com/questions/5307222/how-to-calculate-the-index-lexicographical-order-when-the-combination-is-given

Friday, October 19, 2012

Algoritmo per il calcolo diretto di permutazioni


Le permutazioni, come le combinazioni, di cui ci occuperemo in un prossimo topic, sono concetti matematici particolarmente importanti in quanto alla base di numerosi algoritmi utilizzati nei software più disparati.
Per tale motivo, è molto utile disporre di un buon algoritmo per la generazione di questi oggetti matematici.
In particolare, di seguito, sarà descritto un algoritmo per calcolare in modo diretto una specifica permutazione a partire dalla sua posizione nella lista delle permutazioni con ordine lessicografico (o ordine da dizionario).
Ora, in generale, le permutazioni, come le combinazioni, sono oggetti matematici i cui elementi possono appartenere agli insiemi più disparati. Noi, nel seguito, senza perdere di generalità, ci riferiremo a permutazioni i cui elementi sono numeri interi che vanno da 0 alla lunghezza della permutazione.
In tal modo, quindi, dire che l'elenco delle permutazioni è ordinato lessicograficamente equivale a dire che le permutazioni, interpretando ciascuna di essa nella sua interezza come un unico numero intero, sono elencate in ordine crescente.
Per descrivere l'algoritmo in oggetto, ci riferiremo, per comodità, ad un caso specifico; fermo restando la sua validità nel caso generale.
Il caso specifico a cui ci riferiremo è quello relativo a n=4; per cui, per tale caso, numerandole progressivamente a partire da zero, le permutazioni sono 24 e sono le seguenti:

 0: [0, 1, 2, 3]
 1: [0, 1, 3, 2]
 2: [0, 2, 1, 3]
 3: [0, 2, 3, 1]
 4: [0, 3, 1, 2]
 5: [0, 3, 2, 1]
 6: [1, 0, 2, 3]
 7: [1, 0, 3, 2]
 8: [1, 2, 0, 3]
 9: [1, 2, 3, 0]
10: [1, 3, 0, 2]
11: [1, 3, 2, 0]
12: [2, 0, 1, 3]
13: [2, 0, 3, 1]
14: [2, 1, 0, 3]
15: [2, 1, 3, 0]
16: [2, 3, 0, 1]
17: [2, 3, 1, 0]
18: [3, 0, 1, 2]
19: [3, 0, 2, 1]
20: [3, 1, 0, 2]
21: [3, 1, 2, 0]
22: [3, 2, 0, 1]
23: [3, 2, 1, 0]

Un ruolo cruciale nel nostro algoritmo è svolto dal factoradic (detto anche sistema di numero fattoriale o base fattoriale). Il factoradic è una rappresentazione alternativa di un numero intero.
Vediamo di cosa si tratta. Allo scopo, per il nostro caso n=4, è facile mostrare che il numero 11 può essere rappresentato nel seguente modo:

11 = (1 * 3!) + (2 * 2!) + (1 * 1!) + (0 * 0!) = (1 * 6) + (2 * 2) + (1 * 1) + (0 * 1) = 6 + 4 + 1 + 0 = 11

Ed il suo factoradic risulta essere: [1, 2, 1, 0].

Più in generale, fissato n, è possibile dimostrare che qualsiasi numero compreso tra 0 e (n! - 1), estremi inclusi, può essere rappresentato nella forma appena vista; ossia che $\forall$ index=$0, \cdots, (n! - 1), \exists c_0, c_1, \cdots, c_{n-1}$ interi compresi tra 0 e n-1, tali che: index = $(c_0 * (n-1)!) + (c_1 * (n-2)!) + \cdots + ((c_{n-1}) * 0!)$ e [$c_0, c_1, \cdots, c_{n-1}$] è il factoradic di index con il fissato n.

Per il calcolo del factoradic di index può essere utilizzato il seguente snippet:

for (int i=1; i<=n; ++i) {
     factoradic[n-i] = index % i;
     index /= i;
}

Tornando all'esempio precedente, la lista dei facoradic risulta essere la seguente:

 0: [0, 0, 0, 0]
 1: [0, 0, 1, 0]
 2: [0, 1, 0, 0]
 3: [0, 1, 1, 0]
 4: [0, 2, 0, 0]
 5: [0, 2, 1, 0]
 6: [1, 0, 0, 0]
 7: [1, 0, 1, 0]
 8: [1, 1, 0, 0]
 9: [1, 1, 1, 0]
10: [1, 2, 0, 0]
11: [1, 2, 1, 0]
12: [2, 0, 0, 0]
13: [2, 0, 1, 0]
14: [2, 1, 0, 0]
15: [2, 1, 1, 0]
16: [2, 2, 0, 0]
17: [2, 2, 1, 0]
18: [3, 0, 0, 0]
19: [3, 0, 1, 0]
20: [3, 1, 0, 0]
21: [3, 1, 1, 0]
22: [3, 2, 0, 0]
23: [3, 2, 1, 0]

Una volta calcolato il factoradic è possibile calcolare la corrispondente permutazione.
Per illustrare come calcolare la permutazione partendo dal factoradic appena calcolato, continuiamo ad utilizzare l'esempio che stavamo considerando precedentemente con n=4, index=11 e factoradic=[1, 2, 1, 0].

       index   factoradic     permutation
        11 -> [1, 2, 1, 0] -> [1, 3, 2, 0]

factoradic:      1                        2            1        0
                       |                      |            |        |
                 [0, 1, 2, 3] -> [0, 2, 3] -> [0, 2] -> [0]
                       |                      |            |        |
permutation:    1                      3            2        0

Lo snippet relativo al calcolo della permutazione a partire dal factoradic, in pseudo-codice, è il seguente:

for (int i=0; i<n; i++)
      temp[i] = i;

for (int i=0; i<n; i++) {
      permutation[i] = temp[factoradic[i]];
      remove(temp[factoradic[i]]); // rimuove l'elemento da temp diminuendo anche la dimensione di tale array
}

In tal modo l'obbiettivo è raggiunto: partendo dall'indice e calcolando il factoradic è stato possibile risalire alla permutazione associata.
Inoltre, l'algoritmo illustrato è anche invertibile; ossia, partendo da una determinata permutazione è possibile calcolare il relativo factoradic e da questi risalire all'indice della permutazione. Vediamo come.
Innanzitutto, vediamo come è possibile calcolare il factoradic partendo da una specifica permutazione.
Allo scopo, consideriamo ancora la permutazione: [1, 3, 2, 0].
Consideriamo il primo elemento e contiamo il numero di elementi che lo seguono che sono più piccoli di esso (scrivendo tale numero sotto l'elemento considerato:

[1]   [3, 2, 0]
[1]

Ora, ripetiamo questo processo sui restanti elementi [3, 2, 0]:

[1, 3]   [2, 0]
[1, 2]

Ripetiamo ancora sui restanti:

[1, 3, 2]   [0]
[1, 2, 1]

E sull'ultimo:

[1, 3, 2, 0]
[1, 2, 1, 0]

In tal modo otteniamo il factoradic che volevamo calcolare.
A questo punto è immediato risalire all'indice della permutazione in quanto, proprio per come è stato definito il factoradic, risulta che esso è uguale a:

(1 * 3!) + (2 * 2!) + (1 * 1!) + (0 * 0!) = 6 + 4 + 1 + 0 = 11

In questo modo abbiamo visto anche il funzionamento inverso.
Altro notevole pregio di tale algoritmo è che con esso è immediato realizzare un programma per il calcolo delle permutazioni che lavora in parallelo.
Per il futuro mi riservo di pubblicare sul mio sito il codice sogente di un'implementazione Java relativa a quanto esposto.



Riferimenti Web:

http://msdn.microsoft.com/en-us/magazine/cc163513.aspx

http://msdn.microsoft.com/it-it/magazine/cc163513.aspx

http://msdn.microsoft.com/en-us/library/Aa302371

Wednesday, January 05, 2011

Scambio di due variabili senza la variabile di appoggio

Il metodo classico per lo scambio di due variabili, denotiamole con a e b, prevede l'utilizzo di una terza variabile di appoggio, chiamiamola c, e consiste, sostanzialmente, nell'eseguire in successione le seguenti assegnazioni:

c = a
a = b
b = c

In questo topic, sarà mostrato un metodo alternativo che effettuerà il suddetto scambio senza l'utilizzo della terza variable di appoggio c.
L'idea di tale metodo per variabili numeriche è da attribuirsi al caro amico Giovanni Valentino ed è stato poi, successivamente, da me esteso al caso alfanumerico. Nel prosieguo, quindi, distingueremo i due casi analizzandoli separatamente.

Caso numerico
Dette a e b le variabili numeriche da scambiare, possiamo effettuare lo scambio effettuando in successione le seguenti operazioni:

a = a + b
b = a - b
a = a - b

Come si potrà verificare, tale metodo funziona correttamente per qualsiasi valore numerico che si attribuisce alle variabili a e b.
Passiamo quindi ad esaminare il caso alfanumerico.

Caso alfanumerico
Per esaminare tale caso, al fine di aumentare la chiarezza espositiva e la comprensione in termini pratici dello stesso, faremo riferimento alla sintassi di uno specifico linguaggio di programmazione, sebbene il procedimento possa essere applicato utilizzando qualsiasi altro linguaggio.
Per quanto detto, la sintassi che utilizzeremo è quella del linguaggio Java.
Le operazioni da eseguire, ricalcano le orme del caso numerico e si discostano da questo solo per alcuni dettagli.
Più precisamente, dette a e b le variabili alfanumeriche da scambiare, le operazioni da compiere sono le seguenti:


a = a + b;

// b = a.substring(0, 0 + a.length() - b.length()); Equivale a:
b = a.substring(0, a.length() - b.length());

//a = a.substring(b.length(), b.length() + a.length() - b.length()); Equivale a:
//a = a.substring(b.length(), a.length()); Equivale a:
a = a.substring(b.length());


Anche in questo caso, si potrà facilmente constatare, che il metodo funziona per qualsiasi stringa attribuita alle variabili a e b.

Concludiamo tale topic, osservando che: sebbene il metodo illustrato ottimizza l'utilizzo dello spazio di memoria, esso ha, come rovescio della medaglia, l'aumento del tempo computazionale dovuto alle operazioni che devono essere eseguite.
In definitiva, il suddetto metodo, è equivalente a quello tradizionale e la scelta dell'uno o dell'altro, dipende esclusivamente dal tipo di ottimizzazione che si desidera: più spazio e meno tempo nel caso tradizionale, meno spazio e più tempo per il metodo illustrato. Ovviamente, però, essendo tali ottimizzazioni veramente minime, soprattutto in considerazione della potenza raggiunta dagli attuali computers, la scelta del metodo, in realtà, dipende da fattori dovuti esclusivamente al gusto personale.

Friday, May 22, 2009

Algoritmo per la generazione di un calendario di calcio

In questo topic illustrerò un algoritmo, sin'ora inedito, per la generazione di un calendario di calcio.
L'ideatore di tale algoritmo è Giuseppe Di Falco, un bravo professore di matematica dell'ITC che ho frequentato negli anni ottanta.
Prima di passare alla descrizione vera e propria dell'algoritmo, cercherò di spiegare meglio qual'è il problema che si intende risolvere.
Dato un numero n di squadre, si desidera visualizzare un calendario, suddiviso in n giornate, in cui ciascuna delle n squadre incontra una ed una sola volta tutte le altre.
Ogni giornata sarà costituita da n/2 partite e, nel caso in cui n sia dispari, una squadra riposerà.
Al termine del girone, costituito dall'insieme delle giornate, tutte le squadre dovranno aver sfidato una ed una sola volta tutte le altre ed inoltre, sempre nel caso che il numero di squadre sia dispari, tutte dovranno aver riposato una ed una sola volta.
Ovviamente, il nome delle squadre non è importante: potremo riferirci a ciascuna di esse identificandole con un numero compreso tra 1 e n.
A questo punto, vediamo come funziona l'algoritmo in questione, riferendoci, per fissare le idee, ad un caso specifico.
Per comodità, prendiamo in esame prima il caso in cui n è dispari; quindi, a titolo di esempio, supponiamo n=5.
Scriviamo in verticale i nomi (nel nostro caso, come abbiamo detto, le identifichiamo con numeri) delle squadre:

1
2
3
4
5

Immaginando la suddetta lista come una "striscia" pieghevole, la spezziamo in due "ruotando" in senso antiorario la seconda metà in modo tale che essa assuma la seguente forma:

5
14
23

Quella che abbiamo ottenuto costituisce la prima giornata del calendario: la prima squadra gioca contro la quarta, la seconda contro la terza e la quinta riposa.

Ora, tenendo fissa la forma della nostra stricia, facciamo "slittare" in senso antiorario i nomi delle squadre che la compongono.
Così facendo, essa assumerà la seguente conformazione:

4
53
12

Questa costituisce la seconda giornata del nostro calendario.
Ripetendo tale operazione altre n-2 volte otterremo il girone di "andata" del nostro calendario. Non sarà necessario generare il girone di "ritorno" in quanto esso è identico a quello di andata con il solo scambio dei ruoli tra le squadre che giocano "in casa" e quelle che giocano "fuori casa".
In definitiva, quindi, l'output che otterremo sarà il seguente:


Giornata 1:
1 - 4
2 - 3
Riposa la squadra: 5

Giornata 2:
5 - 3
1 - 2
Riposa la squadra: 4

Giornata 3:
4 - 2
5 - 1
Riposa la squadra: 3

Giornata 4:
3 - 1
4 - 5
Riposa la squadra: 2

Giornata 5:
2 - 5
3 - 4
Riposa la squadra: 1


A questo punto, dovremmo esaminare il caso in cui n è pari. Possiamo notare, però, che se "fissiamo" l'ultima squadra, facendola giocare con la squadra che dovrebbe riposare nel caso n-1, otterremmo in modo del tutto automatico proprio il calendario che desideriamo.
Allora, per fissare le idee, supponiamo n=6. Per quanto detto, il calendario che otterremo sarà il seguente:

Giornata 1:
6 - 5
1 - 4
2 - 3

Giornata 2:
6 - 4
5 - 3
1 - 2

Giornata 3:
6 - 3
4 - 2
5 - 1

Giornata 4:
6 - 2
3 - 1
4 - 5

Giornata 5:
6 - 1
2 - 5
3 - 4

Ovviamente, in ogni caso, il numero totale delle giornate (del solo girone di andata), sarà: n - 1 + (n%2).
Per finire, vediamo un'implementazione in Java, rilasciata sotto Licenza GPL 3, come tutto il codice del software presente in questo blog, del suddetto algoritmo.



/**
* @author Andrea Pannitti
*
*/
public class CalendarioDiCalcio {

/**
* @param args
*/
public static void main(String[] args) {
int n;
//Controllo sul parametro di input
try {
n=Integer.parseInt(args[0]);
if (n<1 || n>99) {
System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");
return;
}
}
catch (Exception e) {
System.out.println("Attenzione: il parametro di input deve essere un numero intero compreso tra 1 e 99!");
return;
}

//Inizializzazione della stringa delle squadre
String StringaSquadre = "";
for (int i=1; i<=n; i++)
StringaSquadre+=(" " + String.valueOf(i)).substring((" " + String.valueOf(i)).length()-2);

//Genera il calendario
for (int i=1; i<=n-1+(n%2); i++) {
System.out.println("Giornata " + i +":");

if (n%2==0)
System.out.println(StringaSquadre.substring((n - 1)* 2) + " - " + StringaSquadre.substring((n - 2) * 2, (n - 1) * 2));
for (int j=0; j<(int)((n-1)/2); j++) {
System.out.println(StringaSquadre.substring(j * 2, (j + 1)* 2) + " - " + StringaSquadre.substring((n - j - 3 + (n%2)) * 2, (n - j - 2 + (n%2)) * 2));
}
if (n%2==1)
System.out.println("Riposa la squadra: " + StringaSquadre.substring((n - 1) * 2));

//Ruota la stringa delle squadre
StringaSquadre = StringaSquadre.substring((n - 2 + (n%2)) * 2, (n - 1 + (n%2)) * 2) + StringaSquadre;
StringaSquadre = StringaSquadre.substring(0, (n - 1 + (n%2)) * 2) + StringaSquadre.substring(n * 2, (n + 1 - (n%2)) * 2);
System.out.println();
}
}
}

Saturday, January 26, 2008

CRC Reverser Java Version

In una sfida di un gioco da Hackers a cui partecipo, il problema da risolvere era trovare una parola chiave a partire dal suo codice hash CRC32.
Allora, cercando su Internet, ho trovato un interessante blog di Bas Westerbaan. Da tale blog è possibile scaricare un programma scritto in python che trova tutte le parole che hanno un determinato codice hash CRC32.
Con questo programma ho risolto il mio problema... ma ora la prossima sfida per me era di tradurre tale programma da Python in Java, il mio linguaggio di programmazione preferito insieme a C# e Visual Basic.
Così, ho appreso le basi del linguaggio python ed ho tradotto tale programma.

Potete scaricare la versione Java di tale programma da qui.

Questo programma, come quello di Bas Westerbaan, è rilasciato sotto licenza GPL 2.

Come Usare il programma: java CrcReverser hash (in decimale o esadecimale con h prefisso, senza hash viene inizializzato automaticamente con 4157704578).

Esempio: java CrcReverser 4157704578 oppure java CrcReverser hf7d18982

Aggiornamento: Potete scaricare la nuova versione con interfaccia utente grafica da qui. Il codice sorgente è qui.




English
In a Hacker's Game challenge which I play, the problem to solve was to find a keyword from its CRC32 hash code.
Then, looking on the Internet, I found an interesting blog of Bas Westerbaan. From this blog is possible to download a program written in python that finds all the words with a specifc CRC32 hash code.
With this program I solved my problem... but now the next challenge for me was to translate this program from Python to Java, my favorite programming language with C# and Visual Basic.
So, I learned the basics of python language and I translated this program.

You can download the Java version of this program from here.

This program, like that of Bas Westerbaan, is released under GPL 2 license.

How to use the program: java CrcReverser hash (in decimal or hexadecimal with h prefix, without hash the default is 4157704578).

Exemple: java CrcReverser 4157704578 or java CrcReverser hf7d18982

Update: You can download the new version with GUI from here. The source code is here.