Visualizza il feed RSS

Titolo provvisorio...

Aggiungi un posto a tavola...

Valuta questo inserimento
di pubblicato il 30-10-2015 alle 15:15 (3155 Visite)
Visto il notevole interesse suscitato dal poker di articoli dedicati al simpatico problemino dei ménages (uno, due, tre e quattro), approfittando a piene mani di tutti i (numerosi) tempi d'attesa e di viaggio aeroferronavali, ho provveduto a risistemare il materiale discusso in un unico articolo in PDF, aggiungendo ove possibile alcune utili note e isolando i banalissimi preliminari matematici dalla presentazione storica del problema, seguita a sua volta da una breve discussione degli algoritmi interessati.

Ho cercato in particolare di chiarire le definizioni e i concetti che troppo spesso risultano insoddisfacenti, approssimativi e sconclusionati nelle fonti più facilmente accessibili sul web e, ahinoi, da qualche anno anche in letteratura: come ad esempio lo sfuggente "vettore d'inversione", del quale semplicemente esistono numerose varianti, non tutte ugualmente trattabili computazionalmente in modo efficiente, come quasi tutti paiono bellamente ignorare.

L'articolo risulta comunque ridotto ai minimi termini rispetto a quanto sarebbe stato necessario approfondire, ed è quindi limitato ad una quarantina di pagine A4: ciò solo grazie allo sforzo costante di rinunciare praticamente ad ogni formalismo non elementare, espungendo sistematicamente tutte le dimostrazioni e gli approfondimenti (sia matematici che computazionali), limitando al minimo indispensabile la discussione sulla complessità degli algoritmi e sui dettagli delle ottimizzazioni implementative.

Se si considera che vengono presentati, discussi e implementati ben sette algoritmi per la generazione di permutazioni, derangements e altri oggetti combinatori, alcuni dei quali fanno uso di tecniche implementative piuttosto avanzate e non intuitive, il tutto passando attraverso oltre mezzo secolo di studio e ricerca in materia di generazione combinatoria, appare chiaro che sarebbe stato ben difficile ottenere una sintesi maggiore senza rinunciare a qualcosa di veramente significativo, pur rimanendo ad un livello meramente divulgativo e descrittivo.

A tale proposito ho inoltre riorganizzato anche i sorgenti, facilitandone la compilazione con i più diffusi ambienti mainstream (Digital Mars, Open Watcom, Visual Studio C++ Express 2010, CMake...) e suddividendo le implementazioni dei singoli algoritmi dai moduli comuni, in modo da renderne più agevole lo studio e le eventuali modifiche.

Per motivi di praticità e limitazioni di banda e capienza, i due files (uno zip per i sorgenti e il pdf dell'articolo) sono condivisi tramite hosting esterno, usando dei mirror nell'eventualità (ahinoi nient'affatto rara) che qualcuno di tali file hoster sparisca in /dev/null dall'oggi al domani.

Sarò grato a chi, di volta in volta, mi segnalerà l'eventuale irraggiungibilità di uno o più di tali siti, o altri problemi di sorta.

PS: in poche ore il numero dei downloads dell'articolo è già il doppio di quelli dei sorgenti. Signori miei, non si tratta di entità concettualmente separate, anche se per comodità si sono predisposti due downloads distinti.
L'articolo illustra il concept dietro i sorgenti, e ne riporta solo brevi estratti semplificati e de-commentati. Non avrebbe senso proporre un listing completo nell'articolo. Ne consegue che, mentre leggete l'articolo stesso, è decisamente il caso di avere anche i sorgenti sottomano. Altrimenti si rischia di perdere la visione d'insieme.
Ergo, o li scaricate entrambi, o nessuno dei due...


Menage.zip (mirror 1)

Menage.pdf (mirror 1)

Commenti