A CAT ALGORITHM FOR THE EXHAUSTIVE GENERATION OF ICE PILES

被引：5

作者：

Massazza, Paolo ^{[1
]}

Radicioni, Roberto ^{[1
]}

机构：

[1] Univ Insubria, Dipartimento Informat & Comunicaz, I-21100 Varese, Italy

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2010年 / 44卷 / 04期

关键词：

Sand pile model; ice pile model; integer partitions; exhaustive generation; CAT algorithms; discrete dynamical systems; SAND PILES;

D O I：

10.1051/ita/2011004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：525 / 543

页数：19

共 8 条

[1] SELF-ORGANIZED CRITICALITY [J].

BAK, P ;

TANG, C ;

WIESENFELD, K .

PHYSICAL REVIEW A, 1988, 38 (01) :364-374

[2]

Brylawski T., 1973, Discrete Mathematics, V6, P201, DOI 10.1016/0012-365X(73)90094-0

[3] Enumeration of sand piles [J].

Corteel, S ;

Gouyou-Beauchamps, D .

DISCRETE MATHEMATICS, 2002, 256 (03) :625-643

[4]

Duchi E, 2007, PU M A, V17, P71

[5] Sandpiles and order structure of integer partitions [J].

Goles, E ;

Morvan, M ;

Phan, HD .

DISCRETE APPLIED MATHEMATICS, 2002, 117 (1-3) :51-64

[6] GAMES ON LINE GRAPHS AND SAND PILES [J].

GOLES, E ;

KIWI, MA .

THEORETICAL COMPUTER SCIENCE, 1993, 115 (02) :321-349

[7] Structure of some sand piles model [J].

Latapy, M ;

Mantaci, R ;

Morvan, M ;

Phan, HD .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :525-556

[8]

Massazza P., 2008, PURE MATH APPL PUMA, V19, P147

← 1 →