We define the Symmetric Ice Pile Model SIPMk(n), a generalization of the Ice Pile Model IPMk(n), and we show an efficient algorithm for generating the symmetric ice piles with n grains. More precisely, we show how to exploit an existing algorithm for generating IPMk(n) in order to generate SIPMk(n) in amortized time O(1) and in space O(√kn).
In this paper, we consider the problem of generating particular unimodal sequences that describe the reachable states of the symmetric version of the wellknown Ice Pile Model IPMk(n), a discrete dynamical system introduced by Goles Morvan and Phan [7] as a restriction of the discrete dynamical model proposed in 1973 by Brylawski [2] in order to study linear partitions of an integer n.
IPMk(n) admits a description in terms of a simple game that simulates the movements of ice grains organized into adjacent columns of decreasing heights. If there are two adjacent columns, say i and i + 1, with heights differing by at least 2, a grain can fall down from column i to column i + 1 (the game starts with n grains stacked in column 0). Moreover, if a column i of height p is separated from a column j of height p − 2 by a plateau of at most k − 1 columns of height p − 1, then a grain can slide from i to j crossing the plateau. IPMk(n) is an extension of the Sand Pile Model SPM(n), in which only the fall rule is permitted. SPM(n) has been widely studied in combinatorics, poset theory, physics, and in the theory of cellular automata to represent granular objects, see [1], [6], [7], [8].
A natural extension of SPM(n) has been introduced [5], [12] in order to fix the lack of symmetry (grains either stay or move to the right). Thus, a grain possibly falls down nondeterministically from column i either to column i − 1 or to column i+1. This new model, called Symmetric Sand Pile Model and denoted by SSPM(n), consists of all the integer sequences describing the reachable states of a system starting with n grains in column 0 (the index of a column can be negative).
Despite the simplicity of this rule, the underlying structure drastically changes. While SPM(n) turns out to be a distributive lattice with exactly one fixed point (the bottom, easily characterized), SSPM(n) is neither a lattice nor admits a unique fixed point. Nevertheless, a characterization of fixed points exists [5, Section 3.2], [12, Th. 2] and their number is known [5, Lemmas 15,16,17].
In this paper we introduce the symmetric version of IPMk(n), denoted by SIPMk(n), where left and right slide moves on plateaux of length smaller than or equal to k − 1 are also permitted, in addition to the left and right fall rules. In particular, we show that SIPMk(n) can be generated by means of a CAT (Constant Amortized Time) algorithm. We recall that CAT algorithms for generating sand and ice piles have been presented in [9] and [10], and that a CAT algorithm for generating symmetric sand piles has been proposed in [11], where a decomposition property of symmetric sand piles in terms of product of sand piles is exploited. We prove that a similar decomposition property holds for symmetric ice piles: this lets us design a CAT algorithm that sequentially generates the elements of SIPMk(n) using O(√kn) space.
In Section 2 we lay down preliminaries such as definitions as well as properties and characteristics of unimodal sequences and generalized unimodal sequences, the combinatorial objects used for modeling symmetric ice piles. We also recall some properties of sand and ice piles, as well as the basics of the CAT algorithm used to generate IPMk(n). In Section 3 we characterize unimodal sequences that can be forms of symmetric ice piles and generalized unimodal sequences that can be configurations of SIPMk(n). These properties are the key for proving that our algorithm is correct and computing its complexity. The algorithm is outlined in Section 4 whereas its complexity is analysed in Section 5. 2
A linear partition of n is a non-increasing sequence of strictly positive integers, s = (s0, . . . , sl), such that Pli=0 si = n; the height, the length and the weight of s are h(s) = s0, l(s) = l + 1 and w(s) = n, respectively. We consider the set LP(n) of linear partitions of n equipped with the negative lexicographic or neglex ordering, <nlex, defined as follows: (s0, . . . , sl) <nlex (t0, . . . , tm) if and only if there exists i, 0 ≤ i ≤ min(l, m) such that si > ti and sj = tj for j < i. A unimodal sequence of n is a sequence of strictly positive integers, a = (a0, . . . , al), such that Pli=0 ai = n and a0 ≤ a1 ≤ . . . ≤ aj ≥ aj+i ≥ . . . ≥ al for some j. The smallest index q such that aq−1 ≤ aq ≥ aq+1 ≥ · · · ≥ al is called the center of a, noted by c(a). Obviously, h(a) = ac(a) and, if a is a constant sequence then c(a) = 0. From here on, for i ≥ 0 we let a<i = (a0, a1 . . . , ai−1) and a≥i = (ai, ai+1, . . . , al). Given h > 1, we indicate by p[h] the sequence (p, p, . . . , p), | {hz } interpreted as a plateau of h columns of height p. The catenation product of sequences is denoted by “ · ”, (a0, . . . , al) · (b0, . . . , bp) = (a0, . . . , al, b0, . . . , bp), and the reversal of a by a = (al, . . . , a0). If a = b · c we say that b and c are a prefix and a suffix of a, respectively.
We equip the set US(n) of unimodal sequences of n with a particular linear order “ < ”. Thus, let a, b ∈ US(n), x1 = h(a), x2 = h(b) and consider the (unique) factorizations a = c · x[1p1] · d, b = e · x[2p2] · f with h(c), h(d) < x1 and h(e), h(f ) < x2. We say that a < b if and only if either (x1 > x2) or (x1 = x2, p1 > p2) or (x1 = x2, p1 = p2, w(d) > w(f )) or (x1 = x2, p1 = p2, w(d) = w(f ), d <nlex f ) or (x1 = x2, p1 = p2, d = f, c <nlex e).
By possibly considering negative indices, we say that (aj, aj+1 . . . , al) is a generalized unimodal sequence of form b = (b0, . . . , bl−j) if and only if b is a unimodal sequence and bi = ai+j, 0 ≤ i ≤ l − j. Index j is the position of a. In other words, a generalized unimodal sequence is obtained by a unimodal sequence by (right- or left-) shifting all its entries by j places. We identify a generalized unimodal sequence by means of a pair (a, j) where a is a unimodal sequence (the form) and j an integer (the position). We also write a to indicate a generalized unimodal sequence whenever the value j does not matter.
We extend the linear order < to the set GUS(n) of generalized unimodal sequences of n by setting (a, i) < (b, j) if and only if either a < b or a = b and i < j. Trivially, one has LP(n) ⊂ US(n) ⊂ GUS(n). If a = (a, j) ∈ GUS(n) then for any i with j ≤ i ≤ j + l(a) − 1 we set a<i = (aj, . . . , ai−1) and a≥i = (ai, . . . , aj+1(a)−1). The right height difference of a = (a, j) at i is defined as δr(a, i) = ai − ai+1 (assume ai = 0 for i > j + l(a) − 1 or i < j). Analogously, the left height difference of a at i is δl(a, i) = ai − ai−1.
We interpret the elements of GUS(n) as blocks of n grains disposed into adjacent columns and define four (partial) functions called moves. Let a = (a, j) ∈ GUS(n), then the right fall of a grain in column i with j ≤ i ≤ j + l(a) − 1 is RFall(a, i) =
⊥ (aj, . . . , ai−1, ai − 1, ai+1 + 1, . . . , aj+l(a)−1) if δr(a, i) > 1, otherwise The function RSlidek allows the crossing of a plateau of length at most k − 1: RSlidek(a, i) = (aj, . . . , ai−1, p, p, . . . , p, ai+k0+2, . . . , aj+l(a)−1)
| k{0+z2 } if there is k0 < k such that a = (aj, . . . , ai−1, p + 1, p, p, . . . , p, p − 1, ai+k0+2, . . . , aj+l(a)−1)
| {kz0 } otherwise RSlidek(a, i) = ⊥. The functions LFall(a, i), and LSlidek(a, i) are defined symmetrically. i b if either b =
Whenever the value k is obvious, we simply write a ⇒ LFall(a, i) or b = RFall(a, i) or b = LSlidek(a, i) or b = RSlidek(a, i). In general, we write a ⇒? b if there is a sequence of moves leading from a to b. 2.1
The Ice Pile Model IPMk(n) consists of the closure of {(n)} under RFall and RSlidek. Linear partitions of IPMk(n) have been characterized combinatorially in [7, Th. 3]. LFall(a,−1)
RFall(a,0) – For any ice pile a with height h one has w(a) ≤ h + k (h+1)h . – For any ice pile a ∈ IPMk(n) one has l(a) ≤ O(√kn). 2
Given a, b ∈ IPMk(n) we say that b dominates a, noted by a ≺ b, if and only if for all e ≥ 0 one has Pie=0 bi ≥ Pie=0 ai. Note that a ≺ b implies b <nlex a. The dominance order ≺ is related to the order induced by ⇒. Indeed, if a ≺ b then b ⇒? a (see [7]).
An ice pile a is called a staircase of height h if and only if either a = h[k0] · (h − j0), with 0 < k0 < k and 0 ≤ j0 ≤ h, or
a = h[k] · (h − 1)[k] · (h − 2)[k] · · · (h − i)[k] · (h − i − 1)[k1] · (h − i − 1 − j) min <nlex (IPMk,h(n)) is with i ≥ 0, 0 ≤ k1 < k and j > 0. We indicate by IPMk,h(n) the set of ice piles of height at most h with n grains, IPMk,h(n) = {a ∈ IPMk(n) | h(a) ≤ h}. Note that for a suitable n with (k + 1)h < n ≤ h + k (h+1)h , the ice pile 2 h[k+1] · (h − 1)[k] · (h − 2)[k] · · · (h − i)[k] · (h − i − 1)[k1] · (h − i − 1 − j). Definition 1. For any h > 0, we call h-critical an ice pile a ∈ IPMk,h−1(n)) such that h[k+1] · a is not an ice pile.
An ice pile a ∈ IPMk,h(n)) is (h + 1)-critical if and only if it has a prefix in the set of ice piles Πh = {a ∈ IPMk(r)|r > 0 ∧ ∃e, 0 ≤ e < h, a = e Y(h − i)[k](h − e)}. i=0 The set of moves of a is M(a) = {i|0 ≤ i ≤ l(a), RFall(a, i) 6= ⊥ or RSlidek(a, i) 6= ⊥}. If a is a staircase or a = min <nlex (IPMk,h(n)) then |M(a)| ≤ 3, indeed M(a) ⊆ {l(a) − j, l(a) − 2, l(a) − 1} for a suitable j ≤ k. If M(a) = ∅ then a is a fixed point . We denote by a(e) the eth ice pile of IPMk(n) (w.r.t. <nlex) and by G(a) the set of ice piles generated from a, G(a) = {b|a ⇒? b}.
Lemma 1. Let a = min <nlex (IPMk,h(n)). Then G(a) = IPMk,h(n).
All ice piles of height h which are smaller than a staircase of height h are (h + 1)-critical: k k k k k1
l(a)−1 l(a)−j l(a)−2
Lemma 2. Let a, b ∈ IPMk,h(n) and suppose that a is a staircase of height h. Then (b <nlex a) ⇐⇒ b is (h + 1)-critical.
Corollary 1. Let a ∈ IPMk,h(n) be a staircase of height h. Then,
G(a) = {b ∈ IPMk,h(n)|b is not (h + 1)-critical}.
For complexity evaluation purposes, we give a bound for the number of ice piles generated by a staircase or by the smallest ice pile of given height. (see fig. 3). Lemma 3. Let a be either min <nlex (IPMk,h(n)) or a staircase in IPMk,h(n). If a is not a fixed point then |G(a)| = Ω( l(ka) ).
k k k
k
Lemma 4. For any e > 0, let ie = max(M(a(e))). Then we have (e) where A(a(e)) = min <nlex {a ∈ IPMk(n) | a<ie+1 = a<ie+1, ie ∈ M (a)}.
A(a(e)) ⇒ie a(e+1) We consider a function Next : IPMk(n) 7→ IPMk(n) such that for e > 0, Next(a(e)) = a(e+1) (Next(a(e)) = ⊥ if a(e) is a fixed point). In [10] it is shown how this function can be implemented so that if a = (n) then, for any fixed integer k, the iteration of the instruction a:=Next(a) (until M(a) 6= ∅) generates IPMk(n) = G((n)) in time O(|G((n))|) (and so is a CAT algorithm) using O(√n) space. More generally, for any a ∈ IPMk(n) one can generate G(a) in time O(|G(a)|). 3
In [5] and [12] the Symmetric Sand Pile Model SSPM(n) (obtained by closing {(n)} with respect to RFall and LFall) has been studied and its relation with SPM(n) analysed. Here we define the Symmetric Ice Pile Model SIPMk(n) as the set of integer sequences (called symmetric ice piles) obtained by closing {(n)} w. r. t. RFall, RSlidek, LFall and LSlidek. Note that if (a, j) = (aj, . . . , al(a)+j−1) ∈ GUS(n) is reached from the initial configuration (n) (all the grains in column 0) then one has j ≤ 0 ≤ l(a) + j − 1, since the evolution rules never empty a column completely (positions j of sequences in SIPMk(n) are nonpositive).
(
(
(
1(
1(
11(
111(
1(
As a matter of fact, symmetric ice piles are closely related to ice piles. Definition 2. Let a = (a0, . . . , al) be a unimodal sequence. Then a is decomposable at i if and only if ai = h(a) and a<i, a≥i are ice piles.
The elements of SIPMk(n) have a form which can be decomposed into the concatenation of a reversed ice pile with an ice pile. More precisely, we extend to SIPMk(n) a decomposition property proved for SSPM(n) in [12, Lemma 3]. Lemma 5. Let a ∈ US(n), then the two following conditions are equivalent: 1. there is an integer i such that a is decomposable at i, with a<i ∈ IPMk(r), a≥i ∈ IPMk(s) and r + s = n; 2. there is an integer j such that (a, j) ∈ SIPMk(n).
Definition 3. For a ∈ US(n) (resp. a ∈ GUS(n)) we denote by D(a) (resp. D(a)) the set of all indices i such that a (resp. a) admits a decomposition at i (or equivalently, is decomposable at i).
Remark 1. Obviously, if a = (a, j) ∈ GUS(n), one has D(a) = D(a) + j = {i + j | i ∈ D(a)}. Note also that D(a) is always an integer interval. Indeed, the set {e | ae = h(a)} is an integer interval [e1, e2] (with e1 = c(a)) and then D(a) = [i1, i2] where : i1 = i2 = (max(e1, e2 − k + 1), (min(e2, e1 + k − 1), max(e1, e2 − (k + 1) + 1) = max(e1, e2 − k), otherwise
min(e2, e1 + (k + 1) − 1) = min(e2, e1 + k), otherwise
Now, we want to determine when a generalized unimodal sequence belongs to SIPMk(n). Following [12], we start defining a unilateral (possibly reversed) ice pile f (a, i) associated with a pair a ∈ GUS(n) and i ∈ D(a).
Definition 4. Let a ∈ GUS(n) and i ∈ D(a). If i ≥ 0, we define f (a, i), called the completion of a at i, as the ice pile s = (s0, s1, . . .) of minimal weight such that s≥i = a≥i. In this case we will call complement of a at i the ice pile c(a, i) = (s0, s1, . . . , si−1).
Similarly, if i < 0, we define f (a, i) as the generalized unimodal sequence s =
(. . . , s−2, s−1, s0) such that s is the reversed ice pile of minimal weight with
s<i = a<i. In this case the complement of a at i is the reversed ice pile c(a, i) =
(si, si+1, . . . , s−1, s0). In either case, w(a, i) denotes the weight of f (a, i).
Example 1. Let n = 21, k = 2, a = (
For any symmetric ice pile a which is decomposable at i, the weight of c(a, i) is
uniquely determined by either a<i (i < 0) or a≥i (i ≥ 0) and easily computed.
Lemma 6. Let a = (a, j) ∈ GUS(n) be decomposable at i. Then w(c(a, i)) can
be computed in time O(
The following Lemma is used for proving Lemma 8, which provides a characterization for the configurations of SIPMk(n).
Lemma 7. Let t ∈ SIPMk(n) such that t = (t, 0) and let a = (a, j) be another generalized unimodal sequence such that j < 0, l(a) = |j| + l(t), a ∈ IPMk(n) and such that for all i with 0 ≤ i < l(t) one has ai ≤ ti. Then a is reachable from t.
Lemma 8. A sequence a = (a, j) ∈ GUS(n) belongs to SIPMk(n) if and only if ∃ i with j ≤ i ≤ l(a) − 1 + j such that a is decomposable at i and w(a, i) ≤ n.
The condition of the previous lemma characterizing generalized unimodal sequences belonging to SIPMk(n), can be replaced by an equivalent (although apparently stronger) condition.
Lemma 9. Let a = (a, j) ∈ GUS(n). Then, there exists an integer i0 ∈ D(a) such that w(a, i0) ≤ n if and only if for all i ∈ D(a), one has w(a, i) ≤ n. Corollary 2. Let a ∈ GUS(n). If 0 ∈ D(a) then a ∈ SIPMk(n).
Lemma 9 also allows to deduce that for all unimodal sequence a, the set S(a) of integers j such that (a, j) is in SIPMk(n) is an integer interval. Corollary 3. Given a ∈ US(n), let j1, j2 be two integers such that (a, j1), (a, j2) ∈ SIPMk(n). Then for all j with j1 ≤ j ≤ j2 one has (a, j) ∈ SIPMk(n).
Our algorithm generates all possible unimodal sequences a that are form of some symmetric ice pile, and, for each form, all integers j such that (a, j) ∈ SIPMk(n). We only need to determine the bounds of S(a).
Corollary 4. Let a ∈ US(n) Then (a, j) ∈ SIPMk(n) if and only if j ∈ [jmin, jmax]
with jmin = min{j|(a, j) ∈ SIPMk(n)} and jmax = max{j|(a, j) ∈ SIPMk(n)}.
For the computation of the two integers jmin, jmax we have:
Corollary 5. Let a ∈ US(n) Then jmin = min{j|(a, j) ∈ SIPMk(n)} and
jmax = max{j|(a, j) ∈ SIPMk(n)} are computed in time O(
Example 2. Let n = 21, k = 2 and a = (
We conclude this section with a slightly different characterization of forms of
symmetric ice piles which is more suitable for our generation algorithm.
Lemma 10. A unimodal sequence a is the form of an element in SIPMk(n)
if and only if a = c · x[p] · d with c¯ ∈ IPMk(t1), d ∈ IPMk(t2), h(c¯), h(d) < x,
t1 +t2 +xp = n and either p < 2k +1 (
Given a unimodal sequence a = c · x[p] · d that is the form of an element in SIPMk(n), the triple (x, p, w(d)) is said the type of a (by Lemma 10 p ≤ 2k + 2). In other words, a triple of integers (x, y, z) is a type for SIPMk(n) if and only if there are a unimodal sequence a = c · x[y] · d, with c¯ ∈ IPMk(n − xy − z) and d ∈ IPMk(z), and an integer j such that (a, j) ∈ SIPMk(n). Obviously one has √n − 1 ≤ x ≤ n, 1 ≤ p ≤ min(bn/xc, 2k + 2) and 0 ≤ r ≤ kx(x − 1)/2 + x − 1. 4
The idea is that of generating in order (with respect to <) all unimodal sequences that are forms of elements in SIPMk(n). By Lemma 10, such forms are the product of three sequences, c · x[p] · d, which satisfy suitable constraints. Thus, we consider all the triples (x, p, r) corresponding to types, then we generate all the forms associated with each type, and lastly, for each form, we compute all the positions of the symmetric ice piles having that form. So, consider a type (x, p, r) and distinguish three cases depending on p.
When p ≤ 2k all the forms can be written as a = c · x[p] · d where c¯ and d are arbitrary ice piles in IPMk,x−1(n − px − r) and IPMk,x−1(r), respectively. In fact, x[j1] · c¯ and x[j2] · d are always ice piles for all j1, j2 ≤ k. By choosing two values such that j1 + j2 = p we can guarantee the existence of a value i such that a<i and a≥i are ice piles. Then, Lemma 5 states that the unimodal sequence c · x[p] · d is the form of an element in SIPMk(n).
Obviously, c · x[p]d 6= c0 · x[p] · d0 if h(c), h(d), h(c0), h(d0) < x and c0 6= c or d0 6= d. Thus, we get all the forms of this type, if we generate all the elements of IPMk,x−1(r) and, for each of these, all the ice piles in IPMk,x−1(n − px − r).
Consider the case p = 2k + 2. In order to get all the forms c · x[2k+2] · d, by
condition (
Lastly, let p = 2k + 1. If r < (k + 1)(x − 1) it is sufficient to generate all d in
IPMk,x−1(r) and (for each of these) all c¯ ∈ IPMk,x−1(n − (2k + 1)x − r). Observe
that d is not x-critical and thus condition (
Once a form c · x[p]d has been generated, all the positions j such that (c · x[p] · d, j) ∈ SIPMk(n) are computed using Corollary 5.
This idea leads immediately to Algorithm 1. We represent ice piles in IPMk(r) as structures with six fields: the number of grains r, the current length, the linear partition (an array of integers), the set of moves (an ordered stack of integers), the integer k and a flag which is on if and only if the ice pile is x-critical. This last field is included only to simplify the computation of the positions.
The algorithm consists of three nested loops (associated with the three entries of a type (x, p, r)). The repeat-loop is used to set the height x of the symmetric ice pile, starting from the initial value n. The for-loop sets the number p of columns of height x, from the the largest allowed value min(bn/xc, 2k + 2) downto 1. Lastly, the while-loop sets the weight r of the ice pile d in c · x[p] · d, from the largest admissible value (the smallest between the number of available grains n − px and either kx(x − 1)/2 or kx(x − 1)/2 + x − 1, depending on p) downto the smallest one (i.e. a value r such that (x, p, r) is a type for SIPMk(n) while (x, p, r − 1) is not).
At each iteration, the value p determines which case of Lemma 10 occurs.
When p < 2k + 1 the call Gen1(m − r,r,x − 1,p,k) generates all symmetric ice piles having the form c · x[p] · d with c¯ ∈ IPMk,x−1(m − r) and d ∈ IPMk,x−1(r). Similarly, if p = 2k + 2 Gen2(m − r,r,x − 1,k) generates all symmetric ice piles having the form c · x[2k+2] · d with c¯ ∈ G(s), and d ∈ G(t), where s and t are the highest staircases in IPMk,x−1(m − r) and IPMk,x−1(r), respectively. Lastly, when p = 2k + 1, the call Gen3(m − r,r,x − 1,k) generates all symmetric ice piles having the form c · x[2k+1] · d and such that c¯ ∈ IPMk,x−1(m − r) or d ∈ IPMk,x−1(r) is not x-critical.
The algorithm halts as soon as a value x is reached such that no symmetric ice pile of height x exists (TooLow(n,k,x) at line 24 returns true iff IPMk,x(n) = ∅).
Procedures Gen [1-3] are easily developed by means of the following functions and procedures. MinIcePile(x,r,k) costructs the smallest ice pile in IPMk,x(r) while Staircase(x,r,k) constructs the highest staircase in IPMk,x(r). Both functions return a reference to an ice pile (the former possibly sets the flag indicating x-criticality). IsStaircase(a) (IsBottom(a)) returns the boolean value true iff a is a staircase (fixed point). The generation of the ice piles c¯ and d which appear in c · x[p] · d is done by means of Next. This function sets its argument to the next ice pile in the neglex order, and returns a reference to it (see Section 2.1). Once the components c, x, p and d of a form are known, the Procedure Positions computes the range of positions for that form.
Example 3. SIPGeneration(
With respect to the space complexity, we point out that the algorithm uses O(√kn) space, since to represent a form c · x[p] · d we need only two ice piles c¯, d (represented by two structures of size O(√kn)) and two integers x, p. Moreover, recall that for any a ∈ IPMk(n) the generation of G(a) requires O(|G(a)|) time and O(√kn) space (see section 2.1).
Procedures MinIcePile and Staircase have a cost which grows as the
length l = O(√kn) of the returned ice pile, whereas IsBottom and
IsStaircase run in time O(
In Procedure SIPGeneration, the repeat-loop iterates O(n) times, the forloop iterates O(k) times and the while-loop iterates O(kn2) times. Then the overall cost is O(k2n3) plus the cost of O(k2n3) calls to Gen[1-3]. Thus, we consider: Lemma 11. Let C(l, r, x, p, k) be the number of symmetric ice piles generated by either Gen1(l,r,x,p,k) (if p ≤ 2k) or Gen3(l,r,x,k) (if p = 2k + 1) or Gen2(l,r,x,k) (if p = 2k + 2). Then, the running time of Gen1(l,r,x,p,k), Gen2(l,r,x,k) and Gen3(l,r,x,k) is O(C(l, r, x, p, k)) + O(√kn).
We can now prove the main result.
Theorem 1. SIPGeneration is a CAT algorithm and uses O(√kn) space.
Proof. Note that all the instructions of SIPGeneration have cost O(
T (n) = O(k2n3) + X O(C(l, r, x, p, k)) = O(k2n3) + O(|SIPMk(n)|). Since k2n3 = O(|SPM(n)|) and |SPM(n)| ≤ |IPMk(n)| ≤ |SIPMk(n)| (see [3] for bounds for |SPM(n)|), SIPGeneration turns out to be a CAT algorithm. With respect to the space complexity, note that the necessary space for storing two ice piles at a time is (O(√kn)). tu
As an extension of this work, it is quite natural to ask whether a similar approach can be applied to deal with the exhaustive generating problem for other (similar) discrete models. In particular, the discrete models BSPM and BIPM (Bidimensional Sand and Ice Pile Model) have been introduced in [4] by adding a further dimension to SPM(n) and IPMk(n), respectively. Thus, the elements of BSPM and BIPM are plane partitions, that is, matrices of nonnegative integers that are nonincreasing from top to bottom and from left to right. These models are not lattices and admit several fixed points but, unlike SIPMk(n), no characterization is known for reachable states and fixed points.