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(root n).

A CAT Algorithm for the Exhaustive Generation of Ice Piles

MASSAZZA, PAOLO;RADICIONI, ROBERTO
2010

Abstract

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(root n).
RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS
Sand pile model / ice pile model / integer partitions / exhaustive generation / CAT algorithms / discrete dynamical systems
File in questo prodotto:
File Dimensione Formato  
MassazzaRadicioniRairo2010.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 327.86 kB
Formato Adobe PDF
327.86 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11383/1719175
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact