1Math::NumSeq::BalancedBUisnearryC(o3n)tributed Perl DocuMmaetnht:a:tNiuomnSeq::BalancedBinary(3)
2
3
4

NAME

6       Math::NumSeq::BalancedBinary -- balanced 1,0 bits
7

SYNOPSIS

9        use Math::NumSeq::BalancedBinary;
10        my $seq = Math::NumSeq::BalancedBinary->new;
11        my ($i, $value) = $seq->next;
12

DESCRIPTION

14       This sequence is integers with 1-bits and 0-bits balanced like opening
15       and closing parentheses.
16
17           2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, ...
18           starting i=1
19
20       Written in binary, a 1-bit is an opening "(" and a 0-bit is a closing
21       ")".
22
23                  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
37       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
41       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
47   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
51           0                         if no node (empty tree)
52           1,left-tree,right-tree    at a node
53
54       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
60           a (root)
61          / \
62         b   c      =>  11001010 [0]
63              \         ab  c d   ^-final zero of encoding omitted
64               d
65
66       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
74       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
80       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
84       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
87   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
92               /\
93              /  \  /\
94             /    \/  \
95            /          \/\
96           ----------------
97            11110001100010
98
99       The mountain range must end at its starting level and must remain at or
100       above its starting level at all times.
101
102       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

FUNCTIONS

107       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
108       classes.
109
110       "$seq = Math::NumSeq::BalancedBinary->new ()"
111           Create and return a new sequence object.
112
113   Random Access
114       "$value = $seq->ith($i)"
115           Return the $i'th balanced binary number.
116
117       "$bool = $seq->pred($value)"
118           Return true if $value is balanced binary.
119
120       "$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
124       "$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

FORMULAS

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
137           11100100             isolated low 1-bit
138           ->                   shifts up
139           11101000
140
141       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
145           1110011000           pair of bits
146           ->                   one shifts up, other drops to low end
147           1110100010
148
149       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
153           1111100111000000     run of bits
154           ->                   one shifts up, rest drop to low end
155           1111101000001010
156                 ^     ^ ^
157                up     low end
158
159       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
163             111000    last 6-bit value, all 1-bits at high end
164           ->
165           10101010    first 8-bit value
166
167       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
172   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
178       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
183           numvalues(z,n) = number of sequences of z "0"s and n "1"s
184                            with remaining 1s >= remaining 0s at all times
185
186           N = numvalues(z-1,n)
187             = how many combinations starting with zero "0..."
188
189           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
193       numvalues() is the "Catalan table" constructed by
194
195           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
201       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
204           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
210       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
214       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

OEIS

218       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
219       this sequence include
220
221           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

SEE ALSO

235       Math::NumSeq, Math::NumSeq::Catalan, Math::NumSeq::Fibbinary
236

HOME PAGE

238       <http://user42.tuxfamily.org/math-numseq/index.html>
239

LICENSE

241       Copyright 2012, 2013, 2014, 2016, 2018, 2019 Kevin Ryde
242
243       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
248       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
253       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/>.
255
256
257
258perl v5.32.1                      2021-01-27   Math::NumSeq::BalancedBinary(3)
Impressum