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

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

DOI : https://doi.org/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},
publisher = {EDP-Sciences},
volume = {44},
number = {4},
year = {2010},
pages = {525-543},
doi = {10.1051/ita/2011004},
mrnumber = {2775410},
language = {en},
url = {http://www.numdam.org/item/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, Volume 44 (2010) no. 4, pp. 525-543. doi : 10.1051/ita/2011004. http://www.numdam.org/item/ITA_2010__44_4_525_0/

[1] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality. Phys. Rev. A 38 (1988) 364-374.

[2] T. Brylawski, The lattice of integer partitions. Discrete Math. 6 (1973) 201-219. | Zbl 0283.06003

[3] S. Corteel and D. Gouyou-Beauchamps, Enumeration of sand piles. Discrete Math. 256 (2002) 625-643. | Zbl 1013.05010

[4] E. Duchi, R. Mantaci, H.D. Phan and D. Rossin, Bidimensional sand pile and ice pile models. PU.M.A. 17 (2007) 71-96.

[5] E. Goles and M.A. Kiwi, Games on line graphs and sand piles. Theoret. Comput. Sci. 115 (1993) 321-349. | Zbl 0785.90120

[6] E. Goles, M. Morvan and H.D. Phan, Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51-64. | Zbl 0998.05005

[7] M. Latapy, R. Mantaci, M. Morvan and H.D. Phan, Structure of same sand piles model. Theoret. Comput. Sci. 262 (2001) 525-556. | Zbl 0983.68085

[8] P. Massazza, A CAT algorithm for sand piles. PU.M.A. 19 (2008) 147-158. | Zbl pre05855081