Partizioni: la saga delle addizioni continua!
di
pubblicato il 08-05-2020 alle 16:08 (657 Visite)
Sono ormai trascorsi più di dieci anni dal primo articolo sulle partizioni su questo blog: un tema che ha sollevato interesse e curiosità negli anni ad ogni nuovo appuntamento.
In questa occasione ci riallacciamo al tema del retrocomputing ed al linguaggio COMAL, una della tante "specialità della Casa", che sta riscuotendo sempre maggiore interesse tra i cultori del computing anni '80, proponendo una implementazione di tre algoritmi che riguardano le partizioni:
1) L'algoritmo euleriano per il calcolo di P(n), il numero totale di partizioni, già visto in passato;
2) L'algoritmo di Zoghbi e Stojmenovic, pubblicato nel 1994, a tutt'oggi uno dei più efficienti in assoluto;
3) Il recente algoritmo di Kelleher e O'Sullivan, pubblicato per la prima volta nel 2009.
PAGE PRINT "***************" PRINT "** EnumParts **" PRINT "***************" DIM part(32) DIM table'parts(33) total:=1 INPUT "Immetti un valore (3-32): ": n num'parts(n) PRINT "P(",n,") = ",table'parts(n+1) acceldesc(n) accelasc(n) END "Fine lavoro." //******************************* //** Subroutines //******************************* PROC acceldesc(n) //******************************* //** Algorithm AccelDesc by //** Zoghbi & Stojmenovic 1994 //******************************* PRINT "AccelDesc(",n,")" IF n<3 THEN PRINT "n deve essere maggiore di 3" RETURN ENDIF total:=1 i:=1 j:=1 FOR i:=2 TO n DO part(i):=1 ENDFOR i part(1):=n display'part(part(),1) WHILE j<>0 DO IF part(j)=2 THEN i:+1 part(j):=1 j:-1 ELSE part(j):-1 m:=part(j) k:=i-j+1 WHILE k>=m DO j:+1 part(j):=m k:-m ENDWHILE IF k=0 THEN i:=j ELSE i:=j+1 IF k>1 THEN j:+1 part(j):=k ENDIF ENDIF ENDIF display'part(part(),i) ENDWHILE ENDPROC acceldesc PROC accelasc(n) //******************************* //** Algorithm AccelAsc by //** Kelleher e O'Sullivan 2014 //******************************* PRINT "AccelAsc(",n,")" IF n<3 THEN PRINT "n deve essere maggiore di 3" RETURN ENDIF total:=1 i:=2 j:=n-1 part(1):=0 WHILE i<>1 DO i:-1 k:=part(i)+1 WHILE 2*k<=j DO part(i):=k j:-k i:+1 ENDWHILE m:=i+1 WHILE k<=j DO part(i):=k part(m):=j display'part(part(),m) k:+1 j:-1 ENDWHILE j:+k-1 part(i):=j+1 display'part(part(),i) ENDWHILE ENDPROC accelasc PROC num'parts(m) //******************************* //** Calcola la funzione P(m) //******************************* table'parts(1):=1 table'parts(2):=1 FOR i:=3 TO m+1 DO sum:=0 sign:=1 omega:=2 j:=1 k:=1 WHILE omega<=i DO omega2:=omega+j sum:+sign*table'parts(i-omega+1) IF omega2<=i THEN sum:+sign*table'parts(i-omega2+1) ENDIF j:+1 k:+3 omega:+k sign:=-sign ENDWHILE table'parts(i):=sum ENDFOR i ENDPROC num'parts PROC display'part(a(),k) PRINT USING "#####": total, PRINT ":", total:+1 FOR i:=1 TO k DO PRINT USING "###": a(i), ENDFOR i PRINT "" ENDPROC display'partIl listato, a prescindere da qualche insignificante modifica nella nomenclatura delle variabili di induzione, è sostanzialmente autoesplicativo e ricalca fedelmente i semplicissimi passaggi illustrati nei due algoritmi così come presentati nel nuovo articolo, con l'aggiunta di un terzo algoritmo ormai molto familiare.
Il lettore in vena di sperimentazioni potrebbe voler considerare l'aggiunta di statement come SELECT OUTPUT "lp:" per inviare l'output su stampante (virtuale) e dovrà comunque armarsi di pazienza: il programma, pur essendo in grado di generare senza errori tutte le 8.349 partizioni di n = 32, richiede tuttavia circa mezz'ora per portare a termine tale elaborazione su un Commodore 64... come di consueto, il programma in COMAL 80 è stato provato con la versione 2.01 su cartridge per C64.
Rimando i lettori, come di consueto, all'articolo completo in PDF (26 pagine) per la presentazione dettagliata degli algoritmi e per tutti i necessari riferimenti alla letteratura, oltre ai richiami organici agli articoli della serie già apparsi sul blog.