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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.