1Math::NumSeq::BalancedBUisnearryC(o3n)tributed Perl DocuMmaetnht:a:tNiuomnSeq::BalancedBinary(3)
2
6 Math::NumSeq::BalancedBinary -- balanced 1,0 bits
7
9 use Math::NumSeq::BalancedBinary;
10 my $seq = Math::NumSeq::BalancedBinary->new;
11 my ($i, $value) = $seq->next;
12
14 This sequence is integers with 1-bits and 0-bits balanced like opening
15 and closing parentheses.
16 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, ...
18 starting i=1
19 Written in binary, a 1-bit is an opening "(" and a 0-bit is a closing
21 ")".
22 value
24 i in binary as parens
25 --- --------- ----------
26 1 10 ()
27 2 1010 () ()
28 3 1100 (())
29 4 101010 () () ()
30 5 101100 () (())
31 6 110010 (()) ()
32 7 110100 (() ())
33 8 111000 ((()))
34 9 10101010 () () () ()
35 10 10101100 () () (())
36 Balanced means the total number of 1s and 0s are the same and when
38 reading from high to low has count(1s) >= count(0s) at all times, which
39 is to say any closing ")" must have a preceding matching open "(".
40 Because the number of 1s and 0s are equal, the width is always an even
42 2*w. The number of values with a given width 2*w is the Catalan number
43 per (Math::NumSeq::Catalan). For example 6-bit values w=6/2=3 is C(3)
44 = (2*3)!/(3!*4!) = 5 many such values, being i=4 through i=8 inclusive
45 shown above.
46 Binary Trees
48 The sequence values correspond to binary trees where each node can have
49 a left and/or right child. Such a tree can be encoded by writing
50 0 if no node (empty tree)
52 1,left-tree,right-tree at a node
53 The "left-tree" and "right-tree" parts are the left and right legs of
55 the node written out recursively. If those legs are both empty (ie.
56 the node is a leaf) then they're empty trees and are "0" giving node
57 "100". Otherwise the node is 1 followed by various more 1s and 0s.
58 For example,
59 a (root)
61 / \
62 b c => 11001010 [0]
63 \ ab c d ^-final zero of encoding omitted
64 d
65 At "a" write 1 and recurse to write its left then right legs. The left
67 leg is "b" so write 1 and the two legs of "b" are empty so write 0,0.
68 That completes the left side of "a" so resume at the right side of "a"
69 which is 1 for "c" and descend to the left and right of "c". The left
70 of "c" is empty so write 0. The right of "c" is "d" so write 1 and the
71 two empty legs of "d" are 0,0. The very final 0 from that right-most
72 leaf "d" is dropped (shown "[0]" above).
73 This encoding can also be applied breadth-first by pushing the left and
75 right descents onto a queue of pending work instead of onto a stack by
76 recursing. In both cases there's an extra final 0 which is dropped.
77 This 0 arises because in any binary tree with K nodes there are K+1
78 empty legs. That would give K many 1-bits and K+1 many 0-bits.
79 In this encoding the balanced binary condition "count 1s >= count 0s"
81 corresponds to there being at least one unfinished node at any time in
82 the traversal (by whichever node order).
83 The "NumSeq" code here acts on values as numbers. Tree encodings like
85 this are probably better handled as a string or list of bits.
86 Mountain Ranges
88 A further usual and attractive interpretation of the opens and closes
89 is as up and down slopes of a mountain range. 1-bit for up, 0-bit for
90 down. For example,
91 /\
93 / \ /\
94 / \/ \
95 / \/\
96 ----------------
97 11110001100010
98 The mountain range must end at its starting level and must remain at or
100 above its starting level at all times.
101 Numerical order of the values means narrower mountain ranges are before
103 wider ones, and two ranges with equal width are ordered by down-slope
104 preceding up-slope at the first place they differ.
105
107 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
108 classes.
109 "$seq = Math::NumSeq::BalancedBinary->new ()"
111 Create and return a new sequence object.
112 Random Access
114 "$value = $seq->ith($i)"
115 Return the $i'th balanced binary number.
116 "$bool = $seq->pred($value)"
118 Return true if $value is balanced binary.
119 "$i = $seq->value_to_i($value)"
121 If $value is balanced binary then return its index i. If $value is
122 not balanced binary then return "undef".
123 "$i = $seq->value_to_i_ceil($value)"
125 "$i = $seq->value_to_i_floor($value)"
126 Return the index i of $value or if $value is not a balanced binary
127 integer then return the i of the next higher or lower value,
128 respectively.
129
131 Next
132 When stepping to the next value, of same bit length, the number of 1s
133 and 0s does not change. The 1s move to make a numerically higher
134 value. The simplest case is an isolated low 1-bit. It must move up
135 one place. For example,
136 11100100 isolated low 1-bit
138 -> shifts up
139 11101000
140 If the low 1 has a 1 above it then that bit must move up and the lower
142 one goes to the low end of the value so as to be the smallest increase.
143 For example
144 1110011000 pair of bits
146 -> one shifts up, other drops to low end
147 1110100010
148 In general the lowest run of 1-bits is changed to have the highest of
150 them move up one place and the rest move down to be a ...101010 pattern
151 at the low end. For example a low run of 3 bits
152 1111100111000000 run of bits
154 -> one shifts up, rest drop to low end
155 1111101000001010
156 ^ ^ ^
157 up low end
158 The final value in a 2*w block has all 1s at the high end. The first
160 of the next bigger block of values is an alternating 1010..10. For
161 example
162 111000 last 6-bit value, all 1-bits at high end
164 ->
165 10101010 first 8-bit value
166 This incrementing is fairly straightforward. Some pseudocode can be
168 found in M.C. Er, "Enumerating Ordered Trees Lexicographically", The
169 Computer Journal, volume 28, number 5, 1985, procedure GenSuc (and Rank
170 and Unrank).
171 Ith
173 As described above there are Catalan(w) many values with 2*w bits. The
174 width of the i'th value can be found by successively subtracting C(1),
175 C(2), etc until reaching a remainder i < C(w). At that point the value
176 is 2*w many bits, being w many "1"s and w many "0"s.
177 In general after outputting some bits of the value (at the high end)
179 there will be a number z many "0"s and n many "1"s yet to be output.
180 The choice is then to output either 0 or 1 and reduce z or n
181 accordingly.
182 numvalues(z,n) = number of sequences of z "0"s and n "1"s
184 with remaining 1s >= remaining 0s at all times
185 N = numvalues(z-1,n)
187 = how many combinations starting with zero "0..."
188 if i < N then output 0
190 if i >= N then output 1 and subtract N from i
191 (which is the "0..." combinations skipped)
192 numvalues() is the "Catalan table" constructed by
194 for z=1 upwards
196 numvalues(z,0) = 1
197 for n = 1 to z
198 numvalues(z,n) = numvalues(z-1,n) # the 0... forms
199 + numvalues(z,n-1) # the 1... forms
200 In each numvalues(z,n) the numvalues(z,n-1) term is the previous
202 numvalues calculated, so a simple addition loop for the table
203 for z=1 upwards
205 t = numvalues(z,0) = 1
206 for n = 1 to z
207 t += numvalues(z-1,n)
208 numvalues(z,n) = t
209 The last entry numvalues(w,w) in each row is Catalan(w), so that can be
211 used for the initial i subtractions seeking the width w. If building
212 or extending a table each time then stop the table at that point.
213 Catalan(w) grows as a little less than a power 4^w so the table has a
215 little more than log4(i) many rows.
216
218 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
219 this sequence include
220 A063171 binary
222 A071152 binary, digits 0,2
223 A085185 base 4
224 A080116 predicate
225 A072643 width
226 A085192 differences
227 A080237 number of low 0 bits
228 A085223 i where single low 0 bit
229 A002054 number of 01 bit pairs in length 2n
230 A057520 value/2, so sans low 0 bit
231 A085183 value sans high 1 and low 0 bits
232 A085184 in base 4
233
235 Math::NumSeq, Math::NumSeq::Catalan, Math::NumSeq::Fibbinary
236
238 <http://user42.tuxfamily.org/math-numseq/index.html>
239
241 Copyright 2012, 2013, 2014, 2016, 2018, 2019 Kevin Ryde
242 Math-NumSeq is free software; you can redistribute it and/or modify it
244 under the terms of the GNU General Public License as published by the
245 Free Software Foundation; either version 3, or (at your option) any
246 later version.
247 Math-NumSeq is distributed in the hope that it will be useful, but
249 WITHOUT ANY WARRANTY; without even the implied warranty of
250 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
251 General Public License for more details.
252 You should have received a copy of the GNU General Public License along
254 with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
255perl v5.32.0 2020-07-28 Math::NumSeq::BalancedBinary(3)