Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T10:06:15.575Z Has data issue: false hasContentIssue false

A CAT algorithm for the exhaustive generation of ice piles

Published online by Cambridge University Press:  28 February 2011

Paolo Massazza
Affiliation:
Università degli Studi dell'Insubria, Dipartimento di Informatica e Comunicazione, Via Mazzini 5, 21100 Varese, Italy; {paolo.massazza,roberto.radicioni}@uninsubria.it
Roberto Radicioni
Affiliation:
Università degli Studi dell'Insubria, Dipartimento di Informatica e Comunicazione, Via Mazzini 5, 21100 Varese, Italy; {paolo.massazza,roberto.radicioni}@uninsubria.it
Get access

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 thatthe 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 timeO(1)and in spaceO( $\sqrt n$ ).

Information

Type
Research Article
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable