Titolo provvisorio...

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'part

Il 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.