Visualizza il feed RSS

Titolo provvisorio...

Ménages... et trois ;-)

Valuta questo inserimento
di pubblicato il 21-08-2015 alle 23:36 (2518 Visite)
Dopo una prima, facile introduzione e un secondo articolo sulla generazione esaustiva delle soluzioni, parliamo ancora del problema dei ménages. Come mostrato esplicitamente ormai in più punti, l'argomento è ben più vasto e interessante di quanto la melensa formulazione originale del problemino potesse far pensare all'ignaro lettore, ed ha connessioni radicate e profonde in numerosissimi settori applicativi, dalla matematica discreta (rook polynomials e dintorni) all'ottimizzazione combinatoria, dalla teoria delle decisioni alle topologie di rete.

Vediamo subito qualche breve considerazione sui tempi di esecuzione degli algoritmi proposti nella scorsa puntata, esclusa per i soliti contingenti motivi di spazio. Analizzando ad esempio l'algoritmo di Akl [01], vediamo che al generico passo k il numero di chiamate ricorsive per il livello successivo, con il parametro k+1, è dato dalla facile ricorrenza:

Formula LaTeX: (1)\ \ \ \begin{cases}d_{n,k}=(n-1)\cdot d_{n-1,k} + (n-k-1)\cdot d_{n-2,k} & \text{ per } 1\leqslant k<n\\d_{n,k} = 1 & \text{ per } k=n\\d_{n,k}=0& \text{ per } k>n\end{cases}

Si tratta di una ricorrenza lineare omogenea di grado due a coefficienti variabili, tra le più semplici.

Avendo volutamente implementato una late rejection che scarta le soluzioni non valide solo al termine della generazione, il numero totale di chiamate rimane invariato rispetto alla versione originale che genera tutti i derangements, ed è dato dalla sommatoria dei dn,k espressi dalla (1).

Formula LaTeX: (2)\ \ \ T_{n}=\sum_{k=1}^{n}\left[(n-1)\cdot d_{n-1,k} + (n-k-1)\cdot d_{n-2,k}\right]

Risolvendo la ricorrenza in questione, si ottiene facilmente la forma chiusa seguente:

Formula LaTeX: (3)\ \ \ T_{n}=\sum_{k=1}^{n}\sum_{r=0}^{n-k}\frac{(-1)^r}{k!}\binom{n-k}{r}(n-r)!\approx (1-e^{-1})n!

Per piccoli valori di n, la divergenza dall'approssimazione asintotica è comunque dell'ordine di un fattore due. Come si vede, l'ordine di grandezza rimane grossolanamente O(n!), ma siamo piuttosto lontani dal valore ideale:

Formula LaTeX: (4)\ \ \ Dc(n)\approx \frac{n!}{e^2}

Infatti, in prima approssimazione, una permutazione ogni tre è un derangement, e a sua volta solo un derangement ogni tre soddisfa le condizioni imposte dal problema dei ménages.

L'algoritmo X di Knuth è puntualmente connotato a livello di runtime nella soluzione all'esercizio 47 della sezione 7.2.1.2 del TAOCP [04]. In particolare, il numero di esecuzioni della sezione X3 (chiaramente dominante) è dato da:

Formula LaTeX: (5)\ \ \ T_{X3}=nN_0+(n-1)N_1+\cdots 1N_{n-1}

Dove gli Ni sono i numeri dei prefissi di lunghezza i che superano il test.

La tabella seguente riporta una semplice comparazione tra il numero di esecuzioni complessive della sezione X3 e il totale delle chiamate ricorsive degli algoritmi di Akl e Rohl [06], per i primi valori di n.

codice:
** n |Rohl_Derange()|Knuth_X()     |Akl_Derange()
**----------------------------------------------
** 3 |4             |6             |8
** 4 |12            |20            |31
** 5 |57            |85            |147
** 6 |323           |452           |853
** 7 |2.185         |2.906         |5.824
** 8 |17.064        |21.868        |45.741
** 9 |150.880       |187.963       |405.845
**10 |1.488.359     |1.813.270     |4.012.711
**11 |16.195.234    |19.377.044    |43.733.976
**12 |192.629.822   |227.046.040   |520.795.003
Osservando i numeretti si potrebbe erroneamente ritenere che nell'algoritmo di Rohl l'introduzione dell'early reject possa conferire un tangibile vantaggio prestazionale su tutti gli altri: tuttavia, non è così. Un profiling accurato dei tempi di esecuzione delle tre implementazioni per valori di n compresi tra 3 e 20, effettuato su sei diverse piattaforme hardware e con una terna di compilatori mainstream (attivando tutte le ottimizzazioni), conferma che (fatto cento il tempo di esecuzione di Akl_Derange()) la prestazione media di Knuth_X() richiede solo il 35,6% di tale tempo, mentre Rohl_Derange() richiede quasi il doppio del tempo, arrivando al 61,4% in media.

Ciò costituisce solo una banale conferma empirica di fatti ben noti a priori. L'overhead delle chiamate ricorsive con lo stack framing e la C calling convention tradizionale prevale ampiamente nel raffronto con Knuth_X(), a dispetto del ridotto numero di iterazioni mostrato in tabella per Rohl. L'eliminazione della ricorsione ripaga sempre, in questo genere di applicazioni, e giustifica pressoché qualsiasi sforzo algoritmico e implementativo.

La trasformazione dell'algoritmo Rohl o Akl in iterativo (o l'implementazione in un linguaggio funzionale idoneo) è comunque lasciata come semplicissimo esercizio per il lettore interessato.

Queste semplici osservazioni da sole giustificano ampiamente il divario prestazionale tra l'algoritmo X e gli altri due, che ribalta totalmente l'impressione generata negli studenti ad una prima lettura dal confronto tra l'apparente "spaghetti code" pieno di goto con l'elegante raffinatezza formale dei due algoritmi ricorsivi classici. Col che ritengo pienamente realizzato il compito didascalico di una tale scelta algoritmica, volta come sempre ad indurre alla riflessione.

Detto questo, vorrei dedicare lo spazio rimanente ad altro. Se è vero che permutazioni e derangement appaiono in migliaia di contesti applicativi, è altrettanto vero che la maggior parte dei programmatori (indifferentemente studenti o practitioner in tutt'altri campi, dal gestionale all'eidomatica al web) sembrano ignorare le risorse bibliografiche primarie e si rivolgono sistematicamente (Murphy docet) alle peggiori e più farraginose soluzioni disponibili nei meandri della Rete, in un fai-da-te devastante prima che esilarante - gravare una generazione esaustiva con complessità di base O(n!) con un unranking quadratico per ogni oggetto generato è purtroppo uno degli svarioni più comuni, senza contare i già sufficientemente esposti limiti degli algoritmi ricorsivi con la maggioranza dei linguaggi imperativi e OOP tradizionali (che taluni geni riescono addirittura a peggiorare portando a spasso ben quattro parametri int/ptr per chiamata sullo stack, e/o infilando nel bel mezzo dell'inner loop una if evitabilissima, come quella di Akl e all'opposto di quelle strutturalmente presenti in Heap o Rohl).

Uno dei metodi di (un)ranking nei quali gli sprovveduti sembrano inciampare più frequentemente è quello basato sui factoradics. Si tratta di uno dei metodi più semplici e intuitivi, peraltro "riscoperto" a più riprese indipendentemente da numerosi matematici nell'arco dello scorso paio di secoli. Ad esempio, con la sua usuale acribia filologica Knuth ci informa che la codifica attribuita normalmente a Lehmer (e spesso lepidamente spacciata come sinonimo unico di "vettore di inversione" ) risale come minimo al "Lehrbuch der Combinatorik" (1901), mentre quella "di Marshall Hall" era già nota a Rodriguez (J. de Math 4) nel 1839!

Va detto subito e senza mezzi termini che si tratta di una scelta assurda e ingiustificata nella maggior parte dei casi: la schiacciante maggioranza degli algoritmi facilmente reperibili basati sui factoradics ha infatti tristissimamente complessità quadratica. Pur esistendo effettivamente alcuni algoritmi di (de)codifica in O(n·log2n) in letteratura, le relative implementazioni risultano scarsissimamente diffuse e in generale sono comunque inutilmente più complesse rispetto ad altre metodologie di ranking, le quali peraltro talora offrono prestazioni asintotiche migliori. Ricordo inoltre che qualsiasi implementazione in C basata sull'uso esplicito dei fattoriali, usando tipi di default, si arresta inesorabilmente a 12! per applicazioni a 32 bit, ed a 20! per quelle a 64. Non si tratta certo di limiti trascurabili.

Sui vettori di inversione, onnipresenti nella manualistica anche di base, non posso che rimandare al TAOCP di Knuth [03], e in particolare agli esercizi 6 e 7 della sezione 5.1.1 del terzo volume, dove l'inclito lettore potrà finalmente apprendere che (al contrario di quanto affermano troppi siti di quart'ordine, e anche qualche manuale cartaceo) sono in uso per le permutazioni almeno quattro distinte versioni del cosiddetto vettore d'inversione, ciascuna delle quali rispetta la fondamentale caratteristica che la somma delle cifre del vettore equivale al numero totale di inversioni presenti nella permutazione.

Seguendo la nomenclatura dello Knuth, si hanno infatti banalmente non meno di quattro modi distinti b, B, c e C (tutti ugualmente "standard") per definire il medesimo concetto di vettore d'inversione:

1) Innanzi tutto, per quantificare gli elementi "fuori posto" in una permutazione e sue derivate, dato il generico elemento ai si possono banalmente contare i valori inferiori ad ai situati alla sua "destra", tali che aj < ai ma j > i; oppure, per converso, è possibile contare i valori maggiori di ai situati alla sua "sinistra", avendosi quindi aj > ai e j < i.

2) Gli elementi nel vettore di inversione possono essere disposti, altrettanto banalmente, in numerosi modi. I più diffusi (non certo unici) sono almeno due: con una corrispondenza diretta di indici, tale che alla locazione i-esima del vettore d'inversione troviamo il numero di inversioni (vedi sopra) corrispondente all'elemento i-esimo della permutazione in esame; o per contro, con una indicizzazione fissa, basata sul valore di ai nella permutazione identità, in modo tale che la locazione zero (risp. uno) del vettore d'inversione contiene sempre e solo il numero di inversioni relative al valore zero (risp. uno), e così via per i successori.

Un banale esempio chiarirà senz'altro le idee anche ai meno fantasiosi.

Formula LaTeX: \begin{align*}P &= \{5,9,1,8,2,6,4,7,3\}\\b(P) &= \langle 2,3,6,4,0,2,2,1,0\rangle & 2+3+6+4+0+2+2+1+0 &=20\\c(P) &= \langle 0,0,0,1,4,2,1,5,7\rangle & 0+0+0+1+4+2+1+5+7 &=20\\B(P) &= \langle 0,0,2,1,3,2,4,2,6\rangle & 0+0+2+1+3+2+4+2+6 &=20\\C(P) &= \langle 4,7,0,5,0,2,1,1,0\rangle & 4+7+0+5+0+2+1+1+0 &=20\end{align*}

Sia data la permutazione P, di nove elementi, con indicizzazione 1-based.
Il vettore di inversione b (noto anche come codifica Hall) riporta in posizione b[5] il valore 0, poiché a sinistra del 5 nella permutazione P non vi sono valori superiori. Per lo stesso motivo, il vettore B[0] riporta il medesimo valore, relativo stavolta a P[0] = 5.
Allo stesso modo c[5] e C[0] (quest'ultima nota come codifica Lehmer) riportano il valore 4, poiché a destra di P[0] = 5 si hanno rispettivamente 1, 2, 4, 3 ossia 4 valori tutti minori di cinque. Il medesimo ragionamento si applica ordinatamente a tutte le altre cifre. Si noti come la somma delle cifre di ogni vettore dà luogo al medesimo risultato (in questo caso, 20) pari al numero totale di coppie invertite, e che i diversi "standard" hanno ovvie conseguenze sulla struttura del vettore e in particolare sulla posizione degli zeri fissi iniziali o finali.

Pare incredibile come la maggior parte delle fonti online (e non) sia incapace di chiarire queste quattro elementari nozioncine!

Si rifletta sulla caratteristica fondante della somma delle cifre: in sostanza, questi vettori altro non sono che composizioni deboli, ossia partizioni (del numero totale di inversioni) in un numero fisso di elementi, che includono anche un numero limitato di zeri (al più, n-1). Questo fatto, spesso sfruttato nelle dimostrazioni, spiega anche la grande varietà di "vettori di inversione" che è possibile definire e utilizzare.

Per divertimento e per giusto contrappasso didattico, ho quindi implementato di sana pianta altri tre algoritmi del nuovo millennio per la generazione di derangements (e non solo), mostrando anche la varietà dei vettori di inversione, sia generici (per tutte le permutazioni) che dedicati (ranking di Mikawa-Tanaka). Peraltro in quest'ultimo caso viene meno anche la caratteristica della somma delle cifre coincidente col numero di inversioni, trattandosi di una codifica del tutto particolare.

L'algoritmo ricorsivo generico di Ganapathi, descritto in [02] e derivato dallo storico Rohl, appartiene di diritto alla categoria dei generatori "universali" di oggetti combinatori, potendo essere facilmente adattato ad almeno una dozzina di contesti diversi, sebbene con prestazioni certo non sbalorditive (il che caratterizza in pratica l'intera famiglia di codesti algoritmi, come prezzo da pagare per la vasta gamma di oggetti combinatori generabili e la grande configurabilità).

L'algoritmo di Effler e Ruskey [07] è stato scelto perché presenta l'interessante caratteristica di generare tutte le permutazioni in ordine di numero di inversioni. Facilmente adattato alla generazione dei soli derangements, per stimolare curiosità e perplessità in ordine ad una delle più simpatiche irregolarità in seno alle permutazioni ristrette, appunto la distribuzione dei derangements in codeste classi di inversione.

Abbiamo appena visto come i vettori di inversione indichino in modo esplicito il numero totale di inversioni di una permutazione. I coefficienti di inversione, ovvero i totalizzatori delle permutazioni di ampiezza n con un numero k dato di inversioni In(k) seguono la ricorrenza:

Formula LaTeX: (6)\ \ \ \begin{cases}I_0(0) = 1 &\\I_n(k) = \sum_{j=0}^{n}[I_{n-1}(k-j)] & \text{ per } n\geq 1\end{cases}

Knuth e altre fonti minori riportano anche una formula chiusa, basata sui numeri pentagonali generalizzati (qui indicati con dj), valida però unicamente per k < n:

Formula LaTeX: \begin{align*}(7)\ \ \ I_n(k) &= \sum_{j=0}^{M}\left[(-1)^j\binom{n+k-d_j-1}{k-d_j}\right]\text{ per }n\geq k\\\\\text{ dove }M &=\left\lceil{\frac{-1+\sqrt{24n+1}}{6}}\right\rceil\end{align*}

Vale la pena di sottolineare nuovamente come k rappresenta il numero totale di coppie di valori "invertite" nella permutazione. Si ha quindi:

Formula LaTeX: (8)\ \ \ 0 \leq k \leq \binom{n}{2}

Dunque il limite superiore per k cresce come un numero triangolare, ed è quindi definitivamente maggiore di n per n > 3, il che di fatto limita l'utilità della formula chiusa nota.

La seguente tabella riporta alcuni valori per In(k).

Formula LaTeX: \begin{matrix}n&k_{max}&I_n(0)&I_n(1)&I_n(2)&I_n(3  )&I_n(4)&I_n(5)&I_n(6)&I_n(7)\\0&0&1&&&&&&&\\1&0&1  &&&&&&&\\2&1&1&1&&&&&&\\3&3&1&2&2&1&&&&\\4&6&1&3&5  &6&5&3&1&\\5&10&1&4&9&15&20&22&20&15\\6&14&1&5&14&  29&49&71&90&101\end{matrix}

La tabella seguente mostra con chiarezza il significato dei coefficienti di inversione con l'intuitivo esempio di I3. Per ogni valore di I3 sono riportate tutte le permutazioni in tale classe di numero di inversioni, e nel medesimo ordine, racchiusi tra parentesi graffe, i corrispondenti elenchi delle coppie che risultano invertite in ciascuna permutazione.

Formula LaTeX: \begin{align*}I_3(0) &= 1 \rightarrow \{123\} & -\\I_3(1) &= 2 \rightarrow \{132\},\{213\} & \{(2,3)\},\{(1,2)\}\\I_3(2) &= 2 \rightarrow \{231\},\{312\} & \{(1,2);(1,3)\},\{(1,3),(2,3)\}\\I_3(3) &= 1 \rightarrow \{321\} & \{(1,2);(1,3);(2,3)\}\end{align*}

Passando ai derangement, ovviamente il numero minimo di coppie da scambiare è dato da:

Formula LaTeX: (9)\ \ \ ID_{min}=\left \lceil \frac{n}{2} \right \rceil

Risulta inoltre sufficientemente ovvio che, se l'ampiezza del derangement è dispari, la permutazione col massimo numero di inversioni definito alla (8) non sarà un derangement, avendo un punto fisso: l'elemento pivot centrale, che non cambia posizione all'inversione. In tali casi vale quindi la relazione d'ordine stretta per il limite superiore di k.

Il lettore potrebbe essere portato ad ipotizzare che, stante il noto rapporto tra numero totale di permutazioni e di derangement per la medesima ampiezza data, anche la distribuzione dei derangement per classi di inversione segua proporzionalmente il medesimo andamento stabilito dalla semplice ricorsione di cui sopra... nulla di più erroneo. Ma niente anticipazioni!

Per concludere, l'algoritmo di Mikawa e Tanaka [05] implementa una metodologia di ranking basata su vettori d'inversione (una specie ovviamente ancora diversa dalle quattro già viste, trattandosi di soli derangements) che opera in O(n·log2n) usando degli alberi binari completi, qui validamente implementati tramite array. In tale contesto ho voluto anche mostrare i relativi vettori d'inversione delle corrispondenti permutazioni, nelle quattro tipologie di base illustrate da Knuth e usando due diversi algoritmi contrapposti (uno efficiente ed elegante, l'altro del tutto deprecabile quanto purtroppo universalmente diffuso).

Mi fermo qui, a causa delle solite limitazioni di spazio, con l'usuale link ai file di testo che contengono il sorgente d'esempio. Ma ovviamente, non finisce qui...

Gli allegati sono stati spostati e riorganizzati a parte. Si veda questo post.




[01] S. G. Akl, "A New Algorithm for Generating Derangements", BIT 20 (1980), 2-7.

[02] P. Ganapathi & B. Rama, "A Versatile Algorithm to Generate Various Combinatorial Structures", {arXiv:1009.4214v2}.

[03] D. E. Knuth, "The Art of Computer Programming, volume 3", Addison-Wesley Professional, (2004), {link}.

[04] D. E. Knuth, "The art of computer programming, volume 4, fascicle 2: Generating all tuples and permutations", Addison-Wesley Professional, (2005).

[05] K. Mikawa & K. Tanaka, "Lexicographic Ranking and Unranking of Derangements in Cycle Notation", Discrete Applied Mathematics 166 (2014) 164-169.

[06] J. S. Rohl, "Generating permutations by choosing", The Computer Journal 21 (1978), no. 4, 302-305.

[07] F. Ruskey & S. Effler, "A CAT Algorithm for Generating Permutations with a Fixed Number of Inversions", Information Processing Letter 86-2 (2003) 107-112.

Commenti