We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model (n), a generalization of the sand pile model (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (n): this lets us design an algorithm which generates all the ice piles of (n) in amortized time O(1) and in space O().
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},
year = {2010},
publisher = {EDP Sciences},
volume = {44},
number = {4},
doi = {10.1051/ita/2011004},
mrnumber = {2775410},
language = {en},
url = {https://www.numdam.org/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 - https://www.numdam.org/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 https://www.numdam.org/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
[1] , and , Self-organized criticality. Phys. Rev. A 38 (1988) 364-374.
[2] , The lattice of integer partitions. Discrete Math. 6 (1973) 201-219. | Zbl
[3] and , Enumeration of sand piles. Discrete Math. 256 (2002) 625-643. | Zbl
[4] , , and , Bidimensional sand pile and ice pile models. PU.M.A. 17 (2007) 71-96.
[5] and , Games on line graphs and sand piles. Theoret. Comput. Sci. 115 (1993) 321-349. | Zbl
[6] , and , Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51-64. | Zbl
[7] , , and , Structure of same sand piles model. Theoret. Comput. Sci. 262 (2001) 525-556. | Zbl
[8] , A CAT algorithm for sand piles. PU.M.A. 19 (2008) 147-158.
Cité par Sources :
