A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza; Roberto Radicioni

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2010)

  • Volume: 44, Issue: 4, page 525-543
  • ISSN: 0988-3754

Abstract

top
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 ).

How to cite

top

Massazza, Paolo, and Radicioni, Roberto. "A CAT algorithm for the exhaustive generation of ice piles." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 44.4 (2010): 525-543. <http://eudml.org/doc/246010>.

@article{Massazza2010,
abstract = {We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model$\mbox\{IPM\}_k$(n), a generalization of the sand pile model$\mbox\{SPM\}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice $\mbox\{IPM\}_k$(n): this lets us design an algorithm which generates all the ice piles of $\mbox\{IPM\}_k$(n) in amortized time O(1) and in space O($\sqrt\{n\}$).},
author = {Massazza, Paolo, Radicioni, Roberto},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {sand pile model; ice pile model; integer partitions; exhaustive generation; CAT algorithms; discrete dynamical systems},
language = {eng},
number = {4},
pages = {525-543},
publisher = {EDP-Sciences},
title = {A CAT algorithm for the exhaustive generation of ice piles},
url = {http://eudml.org/doc/246010},
volume = {44},
year = {2010},
}

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
PB - EDP-Sciences
VL - 44
IS - 4
SP - 525
EP - 543
AB - We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model$\mbox{IPM}_k$(n), a generalization of the sand pile model$\mbox{SPM}$(n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice $\mbox{IPM}_k$(n): this lets us design an algorithm which generates all the ice piles of $\mbox{IPM}_k$(n) in amortized time O(1) and in space O($\sqrt{n}$).
LA - eng
KW - sand pile model; ice pile model; integer partitions; exhaustive generation; CAT algorithms; discrete dynamical systems
UR - http://eudml.org/doc/246010
ER -

References

top
  1. [1] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality. Phys. Rev. A 38 (1988) 364–374. Zbl1230.37103
  2. [2] T. Brylawski, The lattice of integer partitions. Discrete Math. 6 (1973) 201–219. Zbl0283.06003
  3. [3] S. Corteel and D. Gouyou-Beauchamps, Enumeration of sand piles. Discrete Math. 256 (2002) 625–643. Zbl1013.05010
  4. [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. Zbl1224.68062
  5. [5] E. Goles and M.A. Kiwi, Games on line graphs and sand piles. Theoret. Comput. Sci. 115 (1993) 321–349. Zbl0785.90120
  6. [6] E. Goles, M. Morvan and H.D. Phan, Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51–64. Zbl0998.05005
  7. [7] M. Latapy, R. Mantaci, M. Morvan and H.D. Phan, Structure of same sand piles model. Theoret. Comput. Sci. 262 (2001) 525–556. Zbl0983.68085
  8. [8] P. Massazza, A CAT algorithm for sand piles. PU.M.A. 19 (2008) 147–158. Zbl1224.68063

NotesEmbed ?

top

You must be logged in to post comments.