Geodesic
A CAT algorithm for the exhaustive generation of ice piles
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 4, pp. 525-543

Voir la notice de l'article provenant de la source Numdam

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O(n).

DOI : 10.1051/ita/2011004
Classification : 05A17, 68R99
Keywords: sand pile model, ice pile model, integer partitions, exhaustive generation, CAT algorithms, discrete dynamical systems 
@article{ITA_2010__44_4_525_0,
     author = {Massazza, Paolo and Radicioni, Roberto},
     title = {A {CAT} algorithm for the exhaustive generation of ice piles},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {525--543},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {4},
     year = {2010},
     doi = {10.1051/ita/2011004},
     mrnumber = {2775410},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011004/}
}
TY  - JOUR
AU  - Massazza, Paolo
AU  - Radicioni, Roberto
TI  - A CAT algorithm for the exhaustive generation of ice piles
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 525
EP  - 543
VL  - 44
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011004/
DO  - 10.1051/ita/2011004
LA  - en
ID  - ITA_2010__44_4_525_0
ER  - 
%0 Journal Article
%A Massazza, Paolo
%A Radicioni, Roberto
%T A CAT algorithm for the exhaustive generation of ice piles
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 525-543
%V 44
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011004/
%R 10.1051/ita/2011004
%G en
%F ITA_2010__44_4_525_0
Massazza, Paolo; Radicioni, Roberto. A CAT algorithm for the exhaustive generation of ice piles. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 4, pp. 525-543. doi: 10.1051/ita/2011004

Cité par Sources :