Visualizza il feed RSS

Titolo provvisorio...

Un altro giro di valzer, Madame Colette?

Valuta questo inserimento
di pubblicato il 21-08-2015 alle 23:36 (3268 Visite)
Parliamo ancora di ménages.
Nella scorsa puntata abbiamo lasciato la padrona di casa, Donna Letizia, alle prese col problema di mettere a tavola n coppie di invitati, con n numero naturale maggiore di due, rispettando due semplici regole:

1) Uomini e donne occupano posti rigorosamente alternati attorno alla tavola, che ha forma circolare;

2) Nessun coniuge deve occupare alcuna delle due sedie immediatamente adiacenti a quella proprio partner: se la signora J siede al posto i-esimo, il signor j non potrà occupare i posti i-1 e i+1 (ovviamente a meno del modulo), e viceversa.

Abbiamo anche facilmente visto che il numero complessivo di tali soluzioni è dato dalla formuletta seguente, dovuta a Jacques Touchard (1934):

Formula LaTeX: (1)\ \ \ Me(n)\ =\ 2\cdot n!\cdot Dc(n)

Dove Dc(n) (problema ristretto dei ménages) è dato da:

Formula LaTeX: (2)\ \ \ Dc(n) = \sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!

Abbiamo sottolineato come al core di queste configurazioni vi sono dei particolari derangements della permutazione identità a1a2...an, enumerati appunto dalla (2), che ottemperano alla restrizione che nessun ai possa occupare le posizioni i e (i-1) mod n.

Naturalmente spero che a ben pochi lettori sfugga l'importanza applicativa di tale gerarchia di oggetti combinatori: dai protocolli di sicurezza alle policy di distribuzione nelle mesh wireless, dalla logistica alla teoria delle decisioni, all'ottimizzazione lineare... sono migliaia le applicazioni nelle quali si devono evitare configurazioni con punti fissi, ossia che finiscono per mappare un qualsiasi oggetto su se stesso.

La letteratura offre numerosi validi algoritmi per la generazione di derangement, anche ristretti, e trabocca letteralmente di algoritmi per la generazione di permutazioni, ma - specialmente nel caso dei primi - le relative implementazioni non paiono particolarmente note, e per le solite "leggi" (Murphy, Crane, Gresham...) quel poco che si trova facilmente è quasi sempre errato, obsoleto, inadeguato.
L'interesse generale per l'argomento rimane tuttavia elevato, come testimoniano le decine di migliaia di visite ricevute da thread come questo o questo, o più recentemente questo.

In questa puntata mi divertirò a presentare, con il solito ovvio scopo ludico-didattico, un generatore di soluzioni esaustive, limitato a valori ragionevoli (se poi a qualcuno interessa davvero stampare tutti i 382.072.320 di configurazioni per sole otto coppie, ce lo faccia sapere... ) che impiega ben tre possibili generatori alternativi per i derangement ristretti, più un distinto algoritmo per le permutazioni.

I passi della generazione esaustiva sono essenzialmente i seguenti:
  1. Si generano tutti i derangements ristretti secondo le regolette del problema, per un totale pari a Dn come espresso dalla formuletta (2);
  2. Per ogni derangement valido, si generano tutte le permutazioni dell'elenco invitati, per un totale di n!;
  3. Per ogni permutazione, si generano le due soluzioni corrispondenti, assegnando i posti pari ai signori e poi alle signore.

L'assegnazione dei posti avviene con il seguente criterio: i posti dispari vengono assegnati leggendo l'elenco secondo la permutazione corrente, mentre per i posti pari il derangement condizionato viene applicato alla permutazione. Questo garantisce, per ogni soluzione generata, il rispetto dei vincoli del problema. La scelta di partire dai posti pari o dispari è puramente arbitraria e non inficia sulle soluzioni, grazie alla sostanziale simmetria delle configurazioni.

Ecco un esempio di output (ridotto ai minimi termini) per n = 4:
codice:
>> Problema dei menages:
>> esempio didattico di procedura risolutiva esaustiva per 4 coppie.
>> Si hanno in totale 2 derangements e 96 soluzioni.

> Derangement 1 su 2: (2301)
  > Permutazione 1 su 24: (abcd)
    > Soluzione 1 (priorita' alle Signore):
    >>  1 M.me Andre         2 Msr. Bertrand  
    >>  3 M.me Bernard       4 Msr. Bonnet    
    >>  5 M.me Bertrand      6 Msr. Andre     
    >>  7 M.me Bonnet        8 Msr. Bernard   
......
 > Permutazione 24 su 24: (bcda)
    > Soluzione 95 (priorita' alle Signore):
    >>  1 M.me Bernard       2 Msr. Andre     
    >>  3 M.me Bertrand      4 Msr. Bernard   
    >>  5 M.me Bonnet        6 Msr. Bertrand  
    >>  7 M.me Andre         8 Msr. Bonnet    


    > Soluzione 96 (priorita' ai Signori):
    >>  1 Msr. Bernard       2 M.me Andre     
    >>  3 Msr. Bertrand      4 M.me Bernard   
    >>  5 Msr. Bonnet        6 M.me Bertrand  
    >>  7 Msr. Andre         8 M.me Bonnet    

>> Generati in totale 2 derangements e 96 soluzioni.
Moltiplicando tra loro i totali prodotti nei tre passi si ottiene chiaramente il numero di Touchard Me(n). Tali numeri hanno il seguente andamento, per n > 2:

12, 96, 3.120, 115.200, 5.836.320, 382.072.320, 31.488.549.120, 3.191.834.419.200, ...

Dunque siete avvertiti: prima di modificare le #define che limitano la produzione delle soluzioni, dovreste pensarci su decisamente un buon numero di volte. Magari anche il doppio del fattoriale del numero già elevato che state pensando...

La letteratura in materia di permutazioni e derangement è realmente sterminata, e sarebbe impossibile rendere giustizia all'argomento anche impiegando dozzine di articoli del blog. La bibliografia in calce non ha assolutamente la benché minima pretesa, se non di rimandare in modo immediato ad alcuni algoritmi e survey citati più o meno direttamente nel corso del presente articolo. Si passa dal venerabile Knuth ([09], [10]) che all'argomento dedica un intero capitolo nel terzo volume, per tornarvi poi nel secondo fascicolo del quarto volume, al recentissimo lavoro [03] di Arndt che dedica ben due capitoli alla medesima questione (proponendo anche alcune implementazioni di algoritmi di Knuth, in particolare l'algoritmo X che vedremo meglio tra qualche riga), fino alle monografie interamente dedicate alle permutazioni e dintorni, come quella di Miklos Bona [04].
Non c'è testo di combinatorica computazionale, tra quelli qui citati e dozzine di altri, che non dedichi ampio spazio alla questione di generare permutazioni e loro restrizioni! Knuth osservava, con la sua usuale arguzia, che il numero di algoritmi per mettere in disordine una lista è almeno del medesimo ordine di grandezza di quello degli algoritmi di ordinamento...

In generale, codesti algoritmi sono facilmente classificabili in poche grandi famiglie:

1) Generatori esaustivi, quasi sempre ricorsivi, che producono una lista (anche parziale, al bisogno) di oggetti combinatori in un qualche ordine: lessicografico, colessicografico, a minima variazione, plain change ossia bell ringing, per numero di inversioni, per prefissi, eccetera. In genere offrono prestazioni comprese tra O(n2·n!) e O(n!) (in quest'ultimo caso ogni singolo oggetto è generato in O(1), come negli algoritmi loopless), e sono noti alcuni particolari algoritmi in grado di fornire prestazioni addirittura pari a O((n-1)!), producendo in output specifiche codifiche binarie.
Tali generatori, specialmente quelli "universali" ma anche moltissimi single purpose, possono a loro volta essere "filtrati" con early o late rejection, per generare oggetti con particolari restrizioni. In taluni casi, l'algoritmo stesso è invece concepito per generare direttamente tutti e soli gli oggetti interessanti, senza meccanismi di pruning, filtraggio e scarto.

2) Metodi di successione, in grado di generare il "prossimo" oggetto combinatorio secondo un ordinamento prestabilito, di solito in tempo O(n·log2n) o superiore, con poche eccezioni;

3) Metodi di ranking e unranking, che in tempo lineare, ammortizzato (CAT) o O(n·log2n) (ma non mancano eccezioni quadratiche) convertono direttamente un intero nella corrispondente permutazione, o viceversa, sempre secondo un ordinamento prestabilito; sebbene possano essere usati per una generazione esaustiva, sono più spesso validamente impiegati per generare piccoli insiemi di permutazioni o derangement - al limite un singolo oggetto combinatorio, dopo averne scelto l'ordinale corrispondente in modo pseudorandom.

4) Metodi pseudorandom diretti (es. Knuth shuffle), con prestazioni ampiamente accettabili per ottenere un singolo oggetto combinatorio. Occupano molto validamente la loro nicchia applicativa, ma pochi di essi offrono la flessibilità e l'estensibilità necessarie per generare lunghe sequenze di oggetti complessi.

5) Algoritmi paralleli e per GPGPU, ormai da oltre quattro lustri la vera frontiera della ricerca nel campo della generazione combinatoria. Si tratta quasi sempre di algoritmi con basi concettuali innovative rispetto ai tradizionali lavori partoriti fino ad alcune decine di anni fa, e sovente richiedono un poderoso framework di supporto e hardware dedicato.

Tra gli innumerevoli algoritmi disponibili, mi sono divertito a sceglierne ed implementarne quattro dalla categoria degli esaustivi per il nostro generatore di soluzioni al Problema dei Ménage. Di questi, tre sono gli algoritmi alternativi usati per la generazione dei derangements condizionati:
  • Algoritmo X di Knuth (7.2.1.2, Vol. IV fasc. A1 p. 334 del TAOCP [10]): "Lexicographic Permutations with Restricted Prefixes".
    codice:
    /************************************************************************/
    /* Algoritmo X di Knuth (7.2.1.2, Vol. IV fasc. A1 p. 334 del TAOCP):   */
    /* "Lexicographic Permutations with Restricted Prefixes", da un'idea di */
    /* M.C. Er (pubblicata nel 1987).                                       */
    /*                                                                      */
    /* Implementazione ispirata alla versione C++ di Joerg Arndt (FXT).     */
    /************************************************************************/
    void Knuth_X(void)
    {
        derange_t P[MAX_COUPLES];
        derange_t Links[MAX_COUPLES];
        derange_t Undo[MAX_COUPLES];
    
        size_t k;
        derange_t p, q;
    
        /* X1. [Initialize.] */
        for (k = 0; k < Derange.Width; ++k)
        {
            Links[k] = k + 1;
        }
        Links[Derange.Width] = 0;
        k = 1;
    
        /* X2. [Enter level k.] */
    X2:
        p = 0;
        q = Links[0];
    
        /* X3. [test (P[1], ..., P[k])] */
    X3:
        P[k] = q -1;
        /* La funzione di filtro qui viene banalmente implementata in modo diretto: */
        if ((q == k) || (q == 1 + (k % Derange.Width)))
        {
            goto X5;
        }
        else if (k == Derange.Width)
        {
            /* Per uniformita' con le funzioni alternative: */
            memcpy(Derange.D, P+1, Derange.Width * sizeof(derange_t));
            SolveMenage();
            goto X6;
        }
    
        /* X4. [Increase k.] */
        Undo[k]  = p;
        Links[p] = Links[q];
        ++k;
        goto X2;
    
        /* X5. [Increase P[k].] */
    X5:
        p = q;
        q = Links[p];
        if (q != 0)
        {
            goto X3;
        }
    
        /* X6. [Decrease k.] */
    X6:
        --k;
        if (0 == k)
        {
            return;
        }
        p = Undo[k];
        q = P[k] +1;
        Links[p] = q;
        goto X5;
    }
  • Algoritmo ricorsivo di Rohl [18], in versione semplificata e modificata con early rejection.
    codice:
    /************************************************************************/
    /* Algoritmo ricorsivo di Rohl (1978) riveduto e semplificato.          */
    /*                                                                      */
    /* I derangement condizionati sono qui prodotti con una early           */
    /* reject condition, associata alla if() gia' presente strutturalmente  */
    /* entro l'inner loop: caratteristica assai comune in molti algoritmi   */
    /* dell'epoca, a maggior ragione nei piu' generici e flessibili.        */
    /* Non ultimo tra questi lo stesso Heap, impiegato poco oltre - in      */
    /* versione iterativa, per l'occasione.                                 */
    /*                                                                      */
    /* L'eleganza e la concisione di questi algoritmi ne giustificano       */
    /* comunque ancor oggi l'impiego didattico e illustrativo.              */
    /************************************************************************/
    void Rohl_derange(const char len)
    {
        if (len == Derange.Width)
        {
            SolveMenage();
        }
        else
        {
            size_t i;
            for (i = 0; i < Derange.Width; ++i)
            {
                if ((Derange.We[i] == 1) &&
                    (len != i) &&
                    (((len +1) % Derange.Width) != i))
                {
                    Derange.D[len] = i;
                    Derange.We[i]--;
                    Rohl_derange(len +1);
                    Derange.We[i]++;
                }
            }
        }
    }
  • Algoritmo ricorsivo di Akl [02], come esempio di late filtering.
    codice:
    /************************************************************************/
    /* Algoritmo ricorsivo classico di Akl (1981) per i derangements.       */
    /*                                                                      */
    /* Il derangement corrente viene qui convalidato come "menage"          */
    /* solo al termine della generazione.                                   */
    /* In compenso, qui non vi sono salti nell'inner loop.                  */
    /* Complessivamente le prestazioni di questa implementazione            */
    /* restano solo leggermente inferiori a quelle di Rohl_derange()        */
    /* in termini di derangements al secondo, specialmente per              */
    /* piccoli valori di ampiezza.                                          */
    /*                                                                      */
    /************************************************************************/
    void Akl_derange(const char len)
    {
        if (0 == len)
        {
            if (CheckMenage())
            {
                SolveMenage();
            }
        }
        else
        {
            int j;
            /*
            ** Calcolo del valore iniziale di j in funzione del vincolo
            ** fondamentale per i derangements.
            */
            j = ((len -1) == Derange.D[len -1]) ? (len -2) : (len -1);
            for (; j >= 0; --j)
            {
                unsigned int t;
    
                /* SWAP d[j], d[len] */
                t = Derange.D[j];
                Derange.D[j] = Derange.D[len -1];
                Derange.D[len -1] = t;
    
                Akl_derange(len - 1);
    
                /* SWAP d[j], d[len] */
                t = Derange.D[j];
                Derange.D[j] = Derange.D[len -1];
                Derange.D[len -1] = t;
            }
        }
    }

Ho voluto, come si vede, ampiamente privilegiare la tradizione e la semplicità, scegliendo due pietre miliari come Akl (1980) e Rohl (1978) con il loro eccellente stato di servizio nell'informatica applicativa, al fine di presentare ai lettori di ogni età dei veri classici, innegabilmente campioni di eleganza e sintesi.
Riguardo all'effettiva complessità computazionale, mancando qui lo spazio, ne faremo cenno nella prossima puntata.

Per la generazione delle permutazioni dell'elenco, ho scelto invece di trasformare un altro classico assoluto, l'algoritmo di Heap [07], in una routine iterativa secondo le indicazioni del Sedgewick [21]. Una implementazione (necessariamente molto simile, data l'assoluta semplicità dell'algoritmo) di uno Heap iterativo è stata presentata, molti anni dopo, anche da P. Fuchs [05] come Counting QuickPerm().

Gli allegati del'intera serie di articoli sono stati riorganizzati ed espansi. Si veda questo post.

Naturalmente, non finisce qui...

[01] S. G. Akl, "A Comparison of Combination Generation Methods", ACM Trans. Math. Softw. 7 (1981), no. 1, 42-45.

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

[03] J. Arndt, "Matters Computational"

[04] M. Bona, "Combinatorics of Permutations", CRC Press (2012)

[05] P. Fuchs, "Scalable Permutations - QuickPerm"

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

[07] B. R. Heap, "Permutations by Interchanges", The Computer Journal 6 (1963), no. 3, 293-298.

[08] F. M. Ives, "Permutation enumeration: Four new permutation algorithms", Commun. ACM 19 (1976), no. 2, 68-72.

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

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

[11] D. L. Kreher & D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search", CRC Press, (1998), {link}.

[12] D. H. Lehmer, "Teaching combinatorial tricks to a computer", Proceedings of the Symposium on Applications of Mathematics to Combinatorial Analysis 10 (1960), 179-193.

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

[14] A. Nijenhius & H. S. Wilf, "Combinatorial Algorithms", Academic Press, (1975), {download}.

[15] R. J. Ord-Smith, "Generation of permutation sequences: Part 1", Comput. J. 13 (1970), no. 2, 152-155.

[16] R. J. Ord-Smith, "Generation of permutation sequences: Part 2", Comput. J. 14 (1971), no. 2, 136-139.

[17] E. M. Reingold & J. Nievergelt & N. Deo, "Combinatorial Algorithms", Prentice Hall, (1977).

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

[19] F. Ruskey, "Combinatorial Generation", {electronic edition}.

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

[21] R. Sedgewick, "Permutation generation methods", ACM Comput. Surv. 9 (1977), no. 2, 137-164.

[22] R. Stanley, "Enumerative Combinatorics, Vol. 1", Cambridge University Press, (1997), {link}.

[23] H. F. Trotter, "Algorithm 115: Perm", Commun. ACM 5 (1962), no. 8, 434-435.

Commenti