An efficient algorithm for generating symmetric ice piles? Roberto Mantaci1 , Paolo Massazza2 , and Jean-Baptiste Yunès1 1 LIAFA, Université Paris 7 Denis Diderot, Case 7014, 75205 Paris Cedex 13, France Roberto.Mantaci@liafa.univ-paris-diderot.fr, Jean-Baptiste.Yunes@univ-paris-diderot.fr 2 Università degli Studi dell’Insubria, Dipartimento di Scienze Teoriche e Applicate - Sezione Informatica, Via Mazzini 5, 21100 Varese, Italy paolo.massazza@uninsubria.it Abstract. We define the Symmetric Ice Pile Model SIPMk (n), a gen- eralization 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). 1 Introduction In this paper, we consider the problem of generating particular unimodal se- quences that describe the reachable states of the symmetric version of the well- known 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 ? Partially supported by Project M.I.U.R. PRIN 2010-2011: Automi e linguaggi for- mali: aspetti matematici e applicativi 159 R.Mantaci et al. An efficient algorithm for generating symmetric ice piles 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, Sec- tion 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 gen- erating 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 sym- metric 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 Preliminaries A linear partition of n is a non-increasing Pl sequence of strictly positive integers, s = (s0 , . . . , sl ), such that i=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, ti and sj = tj for j < i. A unimodal sequence of n is a sequence of strictly positive integers, a = (a0 , . . . , al ), Pl such that i=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 1, we indicate by p[h] the sequence (p, p, . . . , p), | {z } h 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 ), 160 R.Mantaci et al. An efficient algorithm for generating symmetric ice piles 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 [p ] [p ] (unique) factorizations a = c · x1 1 · d, b = e · x2 2 · 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 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 ad- jacent 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  (aj , . . . , ai−1 , ai − 1, ai+1 + 1, . . . , aj+l(a)−1 ) if δr (a, i) > 1, RFall(a, i) = ⊥ 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 ) | {z } if there is k 0 < k such that k0 +2 a = (aj , . . . , ai−1 , p + 1, p, p, . . . , p, p − 1, ai+k0 +2 , . . . , aj+l(a)−1 ) | {z } k0 otherwise RSlidek (a, i) = ⊥. The functions LFall(a, i), and LSlidek (a, i) are defined symmetrically. i Whenever the value k is obvious, we simply write a ⇒ b if either b = 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 parti- tions of IPMk (n) have been characterized combinatorially in [7, Th. 3]. 161 R.Mantaci et al. An efficient algorithm for generating symmetric ice piles 11 00 00 11 RFall(a,0) 11 00 00 11 0011 00 00 111 11 000 LFall(a,−1) 11 00 11 000 111 00 11 00 111 11 000 −1 0 1 −3 −2 −1 0 1 2 Fig. 1. Moves in GUS(n): RFall and LFall, RSlide3 and LSlide3 . Such theorem implies two upper bounds that are important for our purposes : – For any ice pile a with height h one has w(a) ≤√h + k (h+1)h 2 . – For any ice pile a ∈ IPMk (n) one has l(a) ≤ O( kn). Given a, b ∈ IPMk (n)Pwe say that Pbe dominates a, noted by a ≺ b, if and only e if for all e ≥ 0 one has i=0 bi ≥ i=0 ai . Note that a ≺ b implies b 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 2 , the ice pile min 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 Ye Πh = {a ∈ IPMk (r)|r > 0 ∧ ∃e, 0 ≤ e < h, a = (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 0, let ie = max(M(a(e) )). Then we have i A(a(e) ) ⇒ e a(e+1) (e) where A(a(e) ) = min 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= ∅) gener- ates √ 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 The Symmetric Ice Pile Model 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). (7) 1(6) (6)1 2(5) 1(5)1 (5)2 11(5) 3(4) 2(4)1 1(4)2 (4)3 (5)11 12(4) 11(4)1 3(3)1 2(3)2 1(3)3 1(4)11 (4)21 111(4) 13(3) 12(3)1 11(3)2 3(2)2 2(3)11 2(2)3 1(3)21 (3)31 (4)111 112(3) 111(3)1 22(3) 13(2)1 12(2)2 11(3)11 3(2)11 2(2)21 11(2)3 1(2)31 (3)22 1(3)111 (3)211 122(2) 111(2)2 112(3) 22(2)1 13(1)11 12(2)11 11(2)21 11(1)31 1(2)22 (3)211 2(2)111 (2)221 1112(2) 122(1)1 112(2)1 122(2) 22(1)11 11(2)111 11(1)22 1(2)211 1(1)221 (2)2111 111(2)11 1112(1)1 112(1)11 11(1)211 1(1)2111 Fig. 4. The poset SIPM2 (7) (w.r.t. the order relation induced by ⇒). Figure 4 shows several elements having the same form but with different positions (parentheses are used to indicate column 0). For example (111211, −2), (111211, −3) and (111211, −4) are all in SIPM2 (7). 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 decom- posable at i if and only if ai = h(a) and a 0 such that (a, −4 + δ) ∈ SIPM2 (21) is 1. Indeed, (a, −3) is decomposable at 1 and w((a, −3), 1) = 18 < 21, whereas (a, −2) is decomposable only at j, 2 ≤ j ≤ 4, but with weight w((a, −2), 2) = 23 > 21. On the other hand, (a, −7) ∈ / SIPM2 (21) since it is decomposable only at j, −3 ≤ j ≤ −1 with w((a, −7), −1) = 25 > 21. Therefore (a, j) ∈ SIPM2 (21) if and only if j ∈ [−6, −3]. We conclude this section with a slightly different characterization of forms of symmetric ice piles which is more suitable for our generation algorithm. 166 R.Mantaci et al. An efficient algorithm for generating symmetric ice piles 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 (1) or p = 2k +2 and c̄, d are not x-critical (2) or p = 2k + 1 and at least one of c̄, d is not x-critical (3). 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 √∈ IPMk (z), and an integer j such that (a, j) ∈ SIPMk (n). Obviously one has d n − 1 ≤ x ≤ n, 1 ≤ p ≤ min(bn/xc, 2k + 2) and 0 ≤ r ≤ kx(x − 1)/2 + x − 1. 4 The algorithm 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