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