Visualizza il feed RSS

Titolo provvisorio...

Let's get deranged!

Valuta questo inserimento
di pubblicato il 21-08-2015 alle 23:37 (2607 Visite)
Dopo la terna di articoli dedicata al simpatico problemino dei ménages (uno, due e tre), è opportuno destinare qualche ulteriore riga alla implementazione di esempio fornita nella scorsa puntata.

Un simile sorgente (per quanto meramente illustrativo) di circa 1kLOC, infarcito di una silloge di tecniche di programmazione non banali, brevemente commentato solo nei punti salienti, merita certamente qualche altra spiegazione ad usum delphini, oltre al già fornito chiarimento sui vettori di inversione e relativi indici.

Iniziamo esaminando un dump dell'output prodotto con le #define di default.

codice:
Y:\>derange1
Derangements di 5 (44), algoritmo di Rohl-Ganapathi:
10342   10423   12043   12340   12403   13042   13402   13420   14023   14302   14320
20143   20341   20413   23041   23140   23401   23410   24013   24103   24301   24310
30142   30412   30421   32041   32140   32401   32410   34012   34021   34102   34120   
40123   40312   40321   42013   42103   42301   42310   43012   43021   43102   43120
** Totale: 44 **

Derangements di 5 (44), algoritmo di Effler-Ruskey,
in ordine crescente di numero di inversioni:
  3:    10342   10423   12043   20143
  4:    12340   20341   13042   30142   12403   20413   14023   40123
  5:    23041   13402   30412   24013
  6:    13420   23140   23401   30421   32041   14302   34012   40312   24103   42013
  7:    23410   14320   32140   24301   32401   34021   40321   34102   43012   42103
  8:    24310   32410   34120   42301   43021   43102
  9:    42310   43120
** Totale: 44 **

Derangements di 5 (44), algoritmo di Mikawa-Tanaka:
 Ra Inv    # Cycle Derangement  b-inv B-inv c-inv C-inv ##
---------------------------------------------------------------
  0 10110  3 10342 10342 (  0)  10200 01002 10110 01011  3
  1 10210  4 10432 10423 (  1)  10110 01011 10200 01002  3
  2 11010  3 12043 12043 (  2)  20010 00201 11010 01101  3
  3 11110  4 12340 12340 (  3)  40000 00004 11110 01111  4
  4 11210  5 12430 12403 (  4)  30010 00031 11200 01102  4
  5 12010  4 13042 13402 (  5)  30200 00032 12200 01022  5
  6 12110  5 13240 13420 (  6)  40200 00024 12210 01122  6
  7 12210  6 13420 13042 (  7)  20200 00202 12010 01021  4
  8 13010  5 14032 14320 (  8)  40210 00124 13210 01123  7
  9 13110  6 14230 14302 (  9)  30210 00132 13200 01023  6
 10 13210  7 14320 14023 ( 10)  20110 00211 13000 01003  4
 11 20110  4 20341 23041 ( 11)  23000 00203 22010 00221  5
 12 20210  5 20431 24013 ( 12)  22010 00221 23000 00203  5
 13 21010  4 21043 20143 ( 13)  11010 01101 20010 00201  3
 14 21110  5 21340 23140 ( 14)  42000 00204 22110 01221  6
 15 21210  6 21430 24103 ( 15)  32010 00231 23100 01203  6
 16 22010  5 23041 24301 ( 16)  33010 00133 23200 00223  7
 17 22110  6 23140 24310 ( 17)  43010 00134 23210 01223  8
 18 22210  7 23410 20341 ( 18)  13000 01003 20110 00211  4
 19 23010  6 24031 23410 ( 19)  43000 00034 22210 01222  7
 20 23110  7 24130 23401 ( 20)  33000 00033 22200 00222  6
 21 23210  8 24310 20413 ( 21)  12010 01021 20200 00202  4
 22 30110  5 30241 32401 ( 22)  33100 01033 32200 00232  7
 23 30210  6 30421 34102 ( 23)  32200 00232 33100 01033  7
 24 31010  5 31042 30412 ( 24)  12200 01022 30200 00032  5
 25 31110  6 31240 32410 ( 25)  43100 01034 32210 01232  8
 26 31210  7 31420 34012 ( 26)  22200 00222 33000 00033  6
 27 32010  6 32041 34021 ( 27)  23200 00223 33010 00133  7
 28 32110  7 32140 34120 ( 28)  42200 00224 33110 01133  8
 29 32210  8 32410 30421 ( 29)  13200 01023 30210 00132  6
 30 33010  7 34021 32140 ( 30)  42100 01204 32110 01231  7
 31 33110  8 34120 32041 ( 31)  23100 01203 32010 00231  6
 32 33210  9 34210 30142 ( 32)  11200 01102 30010 00031  4
 33 40110  6 40231 42310 ( 33)  43110 01134 42210 01224  9
 34 40210  7 40321 43120 ( 34)  42210 01224 43110 01134  9
 35 41010  6 41032 40321 ( 35)  13210 01123 40210 00124  7
 36 41110  7 41230 42301 ( 36)  33110 01133 42200 00224  8
 37 41210  8 41320 43021 ( 37)  23210 01223 43010 00134  8
 38 42010  7 42031 43012 ( 38)  22210 01222 43000 00034  7
 39 42110  8 42130 43102 ( 39)  32210 01232 43100 01034  8
 40 42210  9 42310 40312 ( 40)  12210 01122 40200 00024  6
 41 43010  8 43021 42103 ( 41)  32110 01231 42100 01204  7
 42 43110  9 43120 42013 ( 42)  22110 01221 42000 00204  6
 43 43210 10 43210 40123 ( 43)  11110 01111 40000 00004  4
** Totale: 44 **
Il codice, sostanzialmente, esegue le implementazioni dei tre algoritmi di generazione, comparandone visivamente l'output.
  1. Ganapathi et al., "A Versatile Algorithm to Generate Various Combinatorial Structures" [01]. Algoritmo caratterizzato da grande flessibilità, scelto come esempio paradigmatico della sua categoria per configurabilità e versatilità, con ovvio tradeoff dal lato prestazionale. L'upper bound del runtime è infatti connotato da O(|Obj|·k·n), dove |Obj| è la cardinalità del (sotto)insieme di oggetti generati, k la cardinalità della presentazione e n la cardinalità dell'insieme di scelta. Chiaramente, quando k = n o anche semplicemente O(n) e |Obj| = O(n!) come nel caso di permutazioni e derangements, si parla di un algoritmo in O(n2·n!), una prestazione appena accettabile a scopi dimostrativi.
    L'algoritmo completo, fin dall'originale concezione di Rohl negli anni Settanta, nasce chiaramente con ben altri scopi che una generazione esaustiva: può infatti gestire multinsiemi, dunque ripetizioni, disposizioni, regole arbitrarie di filtraggio e generare ordini di output parimenti arbitrari, anche i più bizzarri (ad esempio, prima tutte le permutazioni che iniziano con un numero primo, in ordine ascendente, poi le altre ma in ordine discendente... oppure tutti i prefissi pari in ordine discendente, eccetera). L'implementazione proposta, a differenza del Rohl ridotto utilizzato per i ménage, risulta completa e utilizzabile per intero nella sua versatilità, secondo le indicazioni dell'articolo [01]. Tutto ciò giustifica ampiamente la scelta di tale algoritmo per la presente selezione.
  2. Effler & Ruskey, "A CAT Algorithm for Generating Permutations with a Fixed Number of Inversions" [05]. Il concetto di CAT, tempo costante ammortizzato, è strettamente legato al mondo della generazione combinatoria (così come nel mondo dell'ottimizzazione combinatoria si parla in modo specifico di classe di complessità NP-hard) e la sua introduzione è dovuta allo stesso Ruskey in [04].
    Come da definizione, si parla di CAT quando la computazione, a meno di un trascurabile preprocessing approssimativamente invariante, rimane direttamente proporzionale alla quantità di oggetti generati e quindi sostanzialmente lineare.
    Questo interessante algoritmo ricorsivo, nato per la generazione di permutazioni e immediatamente adattato a generare solo derangements, si basa su una delle statistiche combinatorie più significative, il numero totale di inversioni, alla quale abbiamo già accennato nella scorsa puntata.
  3. Mikawa & Tanaka, "Lexicographic Ranking and Unranking of Derangements in Cycle Notation" [03]. Algoritmo recentissimo, che sfrutta i più innovativi trend per le routine di ranking e unranking, inclusa l'adozione di alberi binari.
    Il tempo di esecuzione si attesta su O(n·log2n) per ogni passo di unranking, grazie ad una codifica sostanzialmente basata sulla rappresentazione ciclica.

Osservando l'output si nota che nel caso 1) si ha null'altro che la banale stampa in ordine di generazione (lessicografico ascendente puro) di tutti i 44 derangements di ampiezza 5.

Nel caso 2), già più interessante, la generazione e la stampa avvengono in ordine di numero di inversioni crescente. Sarà sicuramente istruttivo contare il numero di oggetti generati per ogni dato valore di inversione (una puerile feature la cui giocosa implementazione è lasciata volentieri al divertimento del lettore) e confrontarlo con i valori degli indici di inversione validi per la più generale famiglia delle permutazioni.

Nel caso 3) l'informazione fornita è volutamente molto più completa e strutturata.
L'algoritmo implementato, come accennato, è di tipo ranking()/unranking(): sono fornite quindi funzioni in grado di convertire un numero intero non negativo k (entro un range dato [0, n!-1]) direttamente nel corrispondente derangement in k-esima posizione nell'elenco ordinato lessicograficamente, e la corrispondente funzione in grado di ricavare il rank di un derangement dato.

In questo caso, in realtà, l'ordine lessicografico non si applica direttamente al derangement, ma alla sua cycle notation "in notazione standard". Anche qui, come già notato a proposito dei vettori di inversione, manca totalmente un accordo su cosa sia realmente "standard", tanto che due mostri sacri come Stanley (al quale storicamente si deve la prima definizione di "notazione ciclica standard") e Knuth adottano convenzioni diametralmente opposte!
Come notato anche nei commenti del sorgente, gli autori dell'algoritmo Mikawa e Tanaka usano poi una loro terza notazione, ancora diversa dalle due fondamentali appena menzionate, pur citando quella di Stanley come riferimento.

Cosa sia la cycle notation dovrebbe essere ben noto a tutti gli informatici, essendo la combinatorica elementare nei piani di studio di licei, ITIS e corsi di laurea tecnoscientifici da tempo immemorabile. Si tratta comunque di un'idea semplice e intuitiva, che qui mi limito a richiamare con un banale esempio, senza la pur elementare definizione formale.

Sia data una qualsiasi permutazione in notazione 2-line.

Formula LaTeX: \left(\begin{matrix}1&2&3&4&5&6\\5&1&6&3&4&2\end{m  atrix}\right)

Leggiamo la notazione verticalmente, partendo da sinistra:

Formula LaTeX: \begin{align*}1&\leftarrow 5\\2&\leftarrow 1\\3&\leftarrow 6\\4&\leftarrow 3\\5&\leftarrow 4\\6&\leftarrow 2\\\end{align*}

Questo è l'arcinoto significato della 2-line notation. Riordiniamo adesso le assegnazioni nel modo seguente:

Formula LaTeX: {\color{Red} 1}\leftarrow 5,\ 5\leftarrow 4,\ 4\leftarrow 3,\ 3\leftarrow 6,\ 6\leftarrow 2,\ 2\leftarrow {\color{Red} 1}

Si noti che il ciclo inizia e si conclude col valore marcato in rosso. In questo caso, la permutazione (che è anche un derangement) consta di un solo ciclo, che può essere formalmente scritto in numerosissimi modi equivalenti, dei quali mi limito a fornire un paio di esempi:

Formula LaTeX: \begin{align*}\sigma &= (1,5,4,3,6,2)\\&= 621543\ \text{ Stanley style }\\&= 154362\ \text{ Knuth style }\end{align*}

Come si vede, l'uso dei separatori è opzionale, e in alcuni di questi modi (tra i quali sicuramente le notazioni di Stanley e Knuth) è anche possibile omettere le parentesi, in quanto i cicli sono scritti in modo da anteporre l'elemento minimo (risp. massimo), e poi ordinati in modo crescente in base a tale elemento.

Un altro esempio con un numero maggiore di cicli sarà sicuramente utile.

Formula LaTeX: \begin{pmatrix} 1&2&3&4&5&6&7\\5&7&4&3&1&2&6 \end{pmatrix}

La permutazione data si scompone nei seguenti cicli, in stile Knuth:

Formula LaTeX: (15)(276)(34)\rightarrow1527634

...e in stile Stanley:

Formula LaTeX: (43)(51)(762)\rightarrow4351762

Si noti come le parentesi che delimitano i cicli non sono necessarie con queste due convenzioni. L'algoritmo di Tanaka e Mikawa lavora specificamente sulla notazione ciclica e sulle sue proprietà, usando in sostanza una notazione proprietaria che meglio si adatta all'algoritmo, nella quale l'elemento minimo di ogni ciclo è posposto.

La tabella generata dal software mostra i seguenti elementi, in ordine:
1) Ra: il rank della permutazione, ossia il suo ordinale lessicografico strettamente compreso tra 0 e n! -1;

2) Inv: il corrispondente vettore d'inversione Mikawa-Tanaka;

3) #: la somma delle cifre di tale vettore, per mostrare come in questo caso non vale la proprietà # = numero totale di inversioni;

4) Cycle: la permutazione corrispondente al rank, in notazione ciclica. L'output dell'algoritmo vero e proprio potrebbe tranquillamente terminare qui;

5) Derangement: come omaggio della Casa, ho aggiunto la conversione della notazione ciclica in notazione convenzionale 1-line, seguita dal rank ricalcolato dalla funzione TM_rank() per riscontro;

6) *-inv: altro gentile omaggio, i quattro vettori di inversione convenzionali, seguendo la nomenclatura di Knuth (TAoCP vol. III es. 6 e 7 pag. 592).

7) ##: la somma delle cifre di tali vettori d'inversione, pari in questo caso al numero totale di inversioni e costante per le quattro tipologie di vettore.

Dal punto di vista implementativo, i sorgenti utilizzano una ridotta serie di funzioni helper per la gestione degli alberi binari (ovviamente emulati tramite array, per la massima efficienza) e della puerile lista linkata richiesta dall'algoritmo di Effler-Ruskey per implementare la famosa ed efficacissima tecnica dei "dancing links" di Knuth.

Vengono inoltre presentate, tra l'altro, due distinte implementazioni (una nella sfera del Buono e del Giusto, l'altra in quella del Male) per il calcolo dei vettori di inversione classici, a titolo di exemplum dantesco...

codice:
/************************************************************************/
/* Calcola il vettore di inversione "classico", riferito ai lavori      */
/* di Marshall Hall, in tempo O(nlog2(n)).                              */
/* Basato sostanzialmente sull'esercizio 5.1.1-6 del TAoCP, vol. 3, al  */
/* quale si deve anche la nomenclatura b, B, c, C per le varianti piu'  */
/* diffuse di inversion vector.                                         */
/************************************************************************/
void Knuth_rank(derange_t *b)
{
    size_t j;
    int k;
    uint8_t r, s;
    derange_t x[MAX_DERANGE];

    memset(b, 0, Derange.Width * sizeof(derange_t));

    for (k = log2(Derange.Width); k >= 0; --k)
    {
        for (s = 0; s <= (Derange.Width >> (k+1)); ++s)
        {
            x[s] = 0;
        }

        for (j = 0; j < Derange.Width; ++j)
        {
            r = 1 & (Derange.D[j] >> k);
            s = Derange.D[j] >> (k +1);

            if (r & 1)
            {
                x[s] += 1;
            }
            else
            {
                b[Derange.D[j]] += x[s];
            }
        }
    }

    putchar(' ');
    for (j = 0; j < Derange.Width; ++j)
    {
        x[j] = b[Derange.D[j]];
        putchar(b[j] + '0');
    }
    putchar(' ');
    for (j = 0; j < Derange.Width; ++j)
    {
        putchar(x[j] + '0');
    }
}

/************************************************************************/
/* Calcola il vettore di inversione Lehmer, o factoradic, in O(n^2).    */
/* Presentata come contrappasso dantesco a Knuth_rank(), costituisce un */
/* ottimo esempio di Pessima Programmazione e della legge di Gresham.   */
/*                                                                      */
/* Algoritmo naive non meno del bubblesort, e come esso pervasivamente  */
/* diffuso e terribilmente inefficiente, attira ad un tempo dilettanti  */
/* e practitioners con una regolarita' sinistramente impressionante,    */
/* ad onta dell'esistenza da decenni di algoritmi tree-based in tempo   */
/* O(nlog2(n)) atti a svolgere il medesimo compito - per non dire di    */
/* codifiche assai piu' efficienti computazionalmente come gray, plain  */
/* changes (aka bell ringing), etc.                                     */
/************************************************************************/
void Lehmer_rank(derange_t *b)
{
    size_t in, j;
    int k;
    derange_t x[MAX_DERANGE];

    in = 0;
    memset(b, 0, Derange.Width * sizeof(derange_t));

    for (j = 0; j < Derange.Width; ++j)
    {
        for (k = j +1; k < Derange.Width; ++k)
        {
            b[j] += (Derange.D[k] < Derange.D[j]) ? 1 : 0;
        }
        x[Derange.D[j]] = b[j];
        in += b[j];
    }

    putchar(' ');
    for (j = 0; j < Derange.Width; ++j)
    {
        putchar(b[j] + '0');
    }
    putchar(' ');
    for (j = 0; j < Derange.Width; ++j)
    {
        putchar(x[j] + '0');
    }
    printf(" %2d ", in);
}



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

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

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

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

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

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

Commenti