A CAT ALGORITHM FOR THE EXHAUSTIVEGENERATION OF ICE PILES

We present a CAT (constant amortized time) algorithmfor generating those partitions of n that are in the ice pile modelIPMk(n), a generalization of the sand pile model SPM(n). More precisely,for any fixed integer k, we show that the negative lexicographicordering naturally identifies a tree structure on the lattice IPMk(n):this lets us design an algorithm which generates all the ice piles ofIPMk(n) in amortized time O(1) and in space O(√n)