A generalized ballot sequence is a sequence over the set of non-negative integers where in any of its pre xes each positive integer i occurs at most as often as any integer less than i. We show that the Re ected Gray Code order induces a 3-adjacent Gray code on the set of xed length generalized ballot sequences (that is, Gray code where consecutive sequences di er in at most 3 adjacent positions). Non-trivial e cient generating algorithms for generalized ballot sequences, in both lexicographic and Gray code order, are also presented.
systematically as a general method in [Vaj10, BV05, Vaj01, Vaj07, Vaj08, Vaj11, Sab15, BBP15, Sab17], and our Gray code is in the light of this direction. In the second part of this paper we give constant amortized time exhaustive generating algorithms for generalized ballot sequences for both, lexicographic order and the obtained Gray code. 2
Through this paper, we denote a sequence of length n by an n-tuple (for instance, s1s2 sn), or by an italicized boldface letter (for instance, s and t). For a given sequence s, the notation jsji refers to the number of occurrences of the symbol i in s. For example, if s = 1121313, then jsj1 = 4, jsj2 = 1, and jsj3 = 2.
De nition 2.1. A length n generalized ballot sequence is an integer sequence s = s1s2 : : : sn over the set of non-negative integers with s1 = 0 and js0ji+1 js0ji, for all i, 0 i n 1, in any pre x s0 of s.
Notice that a non-empty pre x of a ballot sequence is still a (smaller length) ballot sequence and we denote by Bn the set of length n ballot sequences. See Table 1 for the set B5.
De nition 2.2. Let s = s1s2 sn and t = t1t2 tn be two distinct integer sequences. Let k be the leftmost position where s; t di er, and u = Pik=11 si = Pik=11 ti: We say that s precedes t in Re ected Gray Code order (RGC order for short), denoted by s t, if either u is even and sk < tk, or u is odd and sk > tk.
We denote by Bn the list of all sequences in Bn with respect to RGC order. Actually, as it is noticed in [Vaj01], it is easy to see that for any k 2 the set of unrestricted k-ary sequences of length n listed in RGC order yields a 1-Gray code (see again [Er84]).
A recursive generating algorithm is said to run in constant amortized time (CAT) if it generates each object in O(1) time, in amortized sense. Such an algorithm is also called a CAT algorithm. Ruskey [Rus03] shows that a recursive generating algorithm is a CAT one if it satis es the following three properties: 1. Each recursive call generates at least one object (there is no dead-end recursive call); 2. The number of computations in each recursive call is proportional to the degree of the call (that is, the number of subsequent recursive calls produced by the current call). The call having zero degree is referred as terminate call. 3. The number of recursive calls having degree one (if any) is O(N ), where N is the number of generated objects.
Before proving the Graycodeness of Bn, rst we need the three following lemmas. The proof of the rst one is straightforward from De nition 2.2.
Lemma 3.1. If s = s1s2 sk 2 Bk and M = maxfs1; s2; : : : ; skg + 1, then 0 and M is, respectively, the smallest and the largest admissible value for sk+1 with respect to s, such that ssk+1 2 Bk+1. Lemma 3.2. Let s = s1s2 sk sn 2 Bn be the last sequence in Bn, with respect to RGC order, having pre x s1s2 sk, for some k n, and let M = maxfs1; s2; : : : ; skg + 1. Then, the sequence s is a length n pre x of the in nite sequence de ned below.
If Pik=1 si is even, and { if M is even, then { if M is odd, then If Pik=1 si is odd, then skM (M + 1)00
, or
.
.
Proof. We begin the proof for the rst claim where Pik=1 si is even. By Lemma 3.1, M is the largest admissible value for sk+1 with respect to s1s2 sk. Since s is the the last sequence in Bn having pre x s1s2 sk and Pk
i=1 si is even, it follows by de nition of RGC order that sk+1 = M . Accordingly for the rest of the sequence, by Lemma 3.1 and de nition of RGC order, the two following possibilities hold: if M is even, then Pik=+11 si is even and this implies sk+2 = (M + 1). Since sk+2 is odd, then Pik=+12 si is odd too, so that sk+3 = 0, which is the smallest admissible value with respect to s1s2 sksk+1sk+2. Continuing in similar way for all succeeding positions, we have 0 = sk+4 = sk+5 = : : :. if M is odd, then Pik=+11 si is odd, and as previously, sk+2 = 0. Continuing in similar way, we have 0 = sk+3 = sk+5 = : : :.
For the second claim, if Pik=1 si is odd, then as previously, sk+1 is the smallest admissible value with respect to s1s2 sk. Continuing in similar way, we have 0 = sk+2 = sk+3 = .
Lemma 3.3. Let t = t1t2 tk tn 2 Bn be the rst sequence in Bn, with respect to RGC order, having pre x t1t2 tk, for some k n, and let N = maxft1; t2; : : : ; tkg + 1. Then, the sequence t is a length n pre x of the in nite sequence de ned below.
If Pik=1 ti is odd and { If N is even, then { If N is odd, then If Pik=1 si is even, then tkN (N + 1)00
.
Proof. If s and t are consecutive in Bn, where s precedes t, and k is the leftmost position where s and t di er, then s is the last sequence in Bn having pre x s1s2 sk, and t is the rst sequence in Bn having pre x t1t2 tk. Besides at position k, by referring to Lemma 3.2 and 3.3, the di erence possibly occurs at position k + 1 and k + 2, since in any case si = ti = 0, for i k + 3.
The proof for the adjacency is by showing that if sk+2 6= tk+2, then sk+1 6= tk+1. By referring to Lemma 3.2 and 3.3, we have the following conditions: or or alternatively, { if M 6= N and M , N have the same parity, then { if M 6= N and M , N have di erent parity, then, skM (M + 1)00 and tkN (N + 1)00 skM (M + 1)00 and
tkN 00 tkN (N + 1)00
tk00 = s1 tkN (N + 1)00 Conditions above clarify that if sk+2 6= tk+2, then sk+1 6= tk+1, which proves the adjacency property.
By [Er84], the length n sequences 000 0 and 010 0 are the rst and last, respectively, length n ballot sequences listed with respect to RGC order. This implies that Bn is also a cyclic Gray code. 4
In this section we give exhaustive generating algorithms for ballot sequences in both lexicographic and RGC order. They require some additional notions that we introduce below.
For s = s1s2 sn 2 Bn we de ne A(s), the set of admissible values with respect to s, as the set of integers a such that sa 2 Bn+1. Recall from Lemma 3.1 that 0 2 A(s) and maxfs1; s2; : : : ; sng + 1 2 A(s), for any such a sequence s. For example, if s = 010213 2 B6, then A(s) = f0; 2; 4g; and A(s0) = f0; 1; 2; 4g, A(s2) = f0; 3; 4g, and A(s4) = f0; 2; 5g. The Parikh vector of s is the sequence c = c0c1 cn 1 with ci = jsji, for i = 0; 1; : : : ; n 1.
Let s 2 Bn be a ballot sequence and c = c0c1 cn 1 its Parikh vector. For an a 2 A(s), the Parikh vector c0 of the ballot sequence sa 2 Bn+1 is simply obtained from c and considering cn = 0, and it is c0 = c0 ca 1(ca + 1)ca+1 cn. However, the set A(sa) of admissible values for sa is a little more complicated, and it is given by the next easy to see proposition.
Proposition 4.1. If s 2 Bn, a 2 A(s) and c is the Parikh vector of s, then
A(sa) =
A(s) [ fa + 1g if ca 1 > ca A(s) [ fa + 1g n fag otherwise: 1;
Every non-empty pre x of a ballot sequence is a smaller size ballot sequence, and our generating algorithm expands recursively each length k ballot sequence into length k + 1 ones, until the desired size is obtained, and the sequence is printed out by procedure Print.
At each generated pre x t, our algorithm needs the set A(t), and this is implemented by two linked lists succ and pred de ned as follows. For an a 2 A(t): succ[a] is the smallest value in A(t) larger than a, if it exists; and is succ[a] = n otherwise. pred[a] is the largest value in A(t) smaller than a, if it exists; and pred[a] = 1 otherwise.
Before the rst recursive call of our generating algorithm, the variables are initialized as follows: the current sequence s is 0 2 B1, the unique generalized ballot sequence of length one, c, the Parikh vector of the current generated sequence is the length n array 100 0, procedure Update(a: integer) c[a] := c[a] + 1; if succ[a] 6= a + 1 then succ[a + 1] := succ[a]; succ[a] := a + 1; pred[succ[a + 1]] := a + 1; pred[a + 1] := a; if a 6= 0 and c[a] = c[a 1] then succ[pred[a]] := succ[a]; pred[succ[a]] := pred[a]; end procedure procedure Restore(a, before, after : integer) c[a] := c[a] 1; succ[before] := a; pred[after ] := a; pred[a] := before; succ[a] := after ; end procedure
For each value a 2 A(s), the lists succ and pred are updated, and after the corresponding recursive call, succ and pred are restored. The obtained lexicographic generating algorithm for Bn is Gen Lex in Figure 2, the main call is Gen Lex(2), and n is a global variable.
Adapting the algorithm Gen Lex according to the considerations in Section 3 we obtain the algorithm Gen Gray in Figure 3 which generates the set Bn in RGC order, that is the list Bn. The main call is Gen Gray(2; 0).
Theorem 4.2. Algorithm Gen Lex and Gen Gray satisfy the CAT desiderata.
Proof. Since f0; M g A(s), letting M = maxfs1; s2; ; sng+1, it follows that each recursive call Gen Lex(k+ 1) or Gen Gray(k + 1, sum) generates at least two ballot sequences s1s2 sk0 and s1s2 skM , so that there is no call of degree one. Each recursive call produces several subsequent recursive calls doing the similar computations with di erent parameters. This means that the number of computations in each recursive call is proportional to the degree of call. So the algorithm satis es the CAT desiderata presented at the end of Section 2.
As a result, Theorem 4.2 con rms the CAT complexity for both algorithms.
Corollary 4.3. Algorithm Gen Lex and Gen Gray are CAT generating algorithms. procedure Gen Gray(k, sum: integer) local a; before; after : integer; if k = n + 1 then Print; else if sum mod 2 = 0 then a := 0; while a < n s[k] := a; before := pred[a]; after := succ[a]; Update(a); Gen Gray(k + 1; sum + a); Restore(a; before; after ); a := succ[a]; end while else a := pred[n]; while a 0 s[k] := a; before := pred[a]; after := succ[a]; Update(a); Gen Gray(k + 1; sum + a); Restore(a; before; after ); a := pred[a]; end while end procedure [Er84]
M. C. Er. On generating the N-ary re ected Gray code.
33(8):739{741, 1984. [GrA53] F. Gray. Pulse code communication. U.S. Patent 2632058, 1953.
IEEE Transaction on Computers, [Kin81] P. Klingsberg. A Gray code for compositions. Journal of Algorithms, 3(1):41-44, 1981. [Rus03] F. Ruskey. Combinatorial Generation, book in preparation, 2003. [Sab15] A. Sabri and V. Vajnovszki. Two Re ected Gray code based orders on some restricted growth sequences.
The Computer Journal, 58(5):1099-1111, 2015. [Sab17] A. Sabri, V. Vajnovszki. More restricted growth functions: Gray codes and exhaustive generations.
Graphs and Combinatorics, 33(3):573-582, 2017.
[Sag01] B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric
Functions, Springer-