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 is the Catalan number
43       C(w) = (2w)!/(w!*(w+1)!).  For example 6-bit values w=6/2=3 gives C(3)
44       = (2*3)!/(3!*4!) = 5 many such values, being i=4 through i=8 inclusive
45       as shown above.  (See Math::NumSeq::Catalan.)
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               d
61              /
62         b   c   =>   11001010 [0]
63          \ /         ab  c d   ^-final zero of encoding omitted
64           a
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 cute interpretation of the opens and closes is as up and down slopes
89       of a mountain range.  1-bit for up, 0-bit for down.  For example,
90
91               /\
92              /  \  /\
93             /    \/  \
94            /          \/\
95           ----------------
96            11110001100010
97
98       The mountain range must end at its starting level and must remain at or
99       above its starting level at all times.
100
101       Numerical order of the values means narrower mountain ranges are before
102       wider ones, and two ranges with equal width are ordered by down-slope
103       preceding up-slope at the first place they differ.
104

FUNCTIONS

106       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
107       classes.
108
109       "$seq = Math::NumSeq::BalancedBinary->new ()"
110           Create and return a new sequence object.
111
112   Random Access
113       "$value = $seq->ith($i)"
114           Return the $i'th balanced binary number.
115
116       "$bool = $seq->pred($value)"
117           Return true if $value is balanced binary.
118
119       "$i = $seq->value_to_i($value)"
120           If $value is balanced binary then return its index i.  If $value is
121           not balanced binary then return "undef".
122
123       "$i = $seq->value_to_i_ceil($value)"
124       "$i = $seq->value_to_i_floor($value)"
125           Return the index i of $value or if $value is not a balanced binary
126           integer then return the i of the next higher or lower value,
127           respectively.
128

FORMULAS

130   Next
131       When stepping to the next value the number of 1s and 0s does not
132       change.  The 1s move to make a numerically higher value.  The simplest
133       case is an isolated low 1-bit.  It must move up one place.  For
134       example,
135
136           11100100             isolated low 1-bit
137           ->                   shifts up
138           11101000
139
140       If the low 1 has a 1 above it then that bit must move up and the lower
141       one goes to the low end of the value.  For example
142
143           1110011000           pair of bits
144           ->                   one shifts up, other drops to low end
145           1110100010
146
147       In general the lowest run of 1-bits is changed to have the highest of
148       them move up one place and the rest move down to be a ...101010 pattern
149       at the low end.  For example a low run of 3 bits
150
151           1111100111000000     run of bits
152           ->                   one shifts up, rest drop to low end
153           1111101000001010
154                 ^     ^ ^
155                up     low end
156
157       The final value in a 2*w block has all 1s at the high end.  The first
158       of the next bigger block of values is an alternating 1010..10.  For
159       example
160
161             111000    last 6-bit value, all 1-bits at high end
162           ->
163           10101010    first 8-bit value
164
165   Ith
166       As described above there are Catalan(w) many values with 2*w bits.  The
167       width of the i'th value can be found by successively subtracting C(1),
168       C(2), etc until reaching a remainder i < C(w).  At that point the value
169       is 2*w many bits, being w many "1"s and w many "0"s.
170
171       In general after outputting some bits of the value (at the high end)
172       there will be a number z many "0"s and n many "1"s yet to be output.
173       The choice is then to output either 0 or 1 and reduce z or n
174       accordingly.
175
176           numvalues(z,n) = number of sequences of z "0"s and n "1"s
177                            with remaining 1s >= remaining 0s at all times
178
179           N = numvalues(z-1,n)
180             = how many combinations starting with zero "0..."
181
182           if i < N  then output 0
183           if i >= N then output 1 and subtract N from i
184                           (which is the "0..." combinations skipped)
185
186       numvalues() is the "Catalan table" constructed by
187
188           for z=1 upwards
189             numvalues(z,0) = 1
190             for n = 1 to z
191               numvalues(z,n) = numvalues(z-1,n)  # the 0... forms
192                              + numvalues(z,n-1)  # the 1... forms
193
194       In each numvalues(z,n) the numvalues(z,n-1) term is the previous
195       numvalues calculated, so a simple addition loop for the table
196
197           for z=1 upwards
198             t = numvalues(z,0) = 1
199             for n = 1 to z
200               t += numvalues(z-1,n)
201               numvalues(z,n) = t
202
203       The last entry numvalues(w,w) in each row is Catalan(w), so that can be
204       used for the initial i subtractions seeking the width w.  If building
205       or extending a table each time then stop the table at that point.
206
207       Catalan(w) grows as a little less than a power 4^w so the table has a
208       little more than log4(i) many rows.
209

SEE ALSO

211       Math::NumSeq, Math::NumSeq::Catalan, Math::NumSeq::Fibbinary
212

HOME PAGE

214       <http://user42.tuxfamily.org/math-numseq/index.html>
215

LICENSE

217       Copyright 2012, 2013, 2014 Kevin Ryde
218
219       Math-NumSeq is free software; you can redistribute it and/or modify it
220       under the terms of the GNU General Public License as published by the
221       Free Software Foundation; either version 3, or (at your option) any
222       later version.
223
224       Math-NumSeq is distributed in the hope that it will be useful, but
225       WITHOUT ANY WARRANTY; without even the implied warranty of
226       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
227       General Public License for more details.
228
229       You should have received a copy of the GNU General Public License along
230       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
231
232
233
234perl v5.28.0                      2014-06-29   Math::NumSeq::BalancedBinary(3)
Impressum