NAME
Math::NumSeq::BalancedBinary -- balanced 1,0 bits
SYNOPSIS
use Math::NumSeq::BalancedBinary;
my $seq = Math::NumSeq::BalancedBinary->new;
my ($i, $value) = $seq->next;DESCRIPTION
This sequence is integers with 1-bits and 0-bits balanced like parentheses,
starting i=1
2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, ...Written in binary it's as if a 1-bit is an opening "(" and a 0-bit is a closing ")".
i binary parens
--- -------- ----------
1 10 ()
2 1010 () ()
3 1100 (())
4 101010 () () ()
5 101100 () (())
6 110010 (()) ()
7 110100 (() ())
8 111000 ((()))
9 10101010 () () () ()
10 10101100 () () (())Balanced means the total number of 1s and 0s are the same, and reading from high to low has count 1s >= count 0s at all times, ie. no closing ")" without a preceding matching open "(".
Because the number of 1s and 0s are equal the width is always an even 2*n. The number of values with a given width is the Catalan number (2n)!/(n!*(n+1)!). For example as shown above there are 5 values with 6 bits, per Catalan(6/2)=5.
Binary Trees
These values correspond to binary trees where each node may have a left and/or right child. Such a tree can be encoded by writing
0 if no node (empty tree)
1,left,right at a nodeThe "left" and "right" parts are the left and right legs of the node written out recursively. If those legs are both empty (the node is a leaf) then they're empty and are "0" each, otherwise more 1s and 0s. For example, going depth-first,
d
/
b c => 11001010[0]
\ / ab cd ^-final zero of encoding omitted
a At "a" write 1 and recurse to write its left and right legs. The left leg is "b" so write 1 and its two legs are empty so write 0,0. That completes the "b" sub-tree so resume at the right leg of "a" which is a 1 for "c". The left of "c" is empty so write 0. The right of "c" is "d" so write 1 and the two empty legs of "d" are 0,0. The very final 0 is dropped.
This encoding can be applied breadth-first too by pushing the left and right descents onto a queue of pending work (instead of a stack by recursing). In both cases there's an extra 0 at the end which is dropped. It arises because in any binary tree of K nodes there are K+1 empty legs.
Int this encoding the balanced binary condition "count 1s >= count 0s" corresponds to there being at least one unfinished node at any time in the traversal (by whatever node order).
The code here acts on values as numbers but for encodings like this a list or string of bits would be more use.
FUNCTIONS
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
Random Access
$value = $seq->ith($i)-
Return the
$i'th balanced binary number. $i = $seq->value_to_i($value)-
If
$valueis balanced binary then return its index i. If$valueis not balanced binary then returnundef. $i = $seq->value_to_i_ceil($value)$i = $seq->value_to_i_floor($value)-
Return the index i of
$valueor if$valueis not a balanced binary integer then return the i of the next higher or lower value, respectively. $bool = $seq->pred($value)-
Return true if
$valueis balanced binary.
FORMULAS
Next
When stepping to the next value the number of 1s and 0s does not change (within a width 2*w block). The 1s move around to make a numerically higher value. The simplest is an isolated lowest 1-bit, it must move up one place. For example,
11100100
->
11101000If the low 1 has a 1 above it then that bit must move up and the low bit goes to the end of the value. For example
1110011000
->
1110100010In general the lowest run of 1-bits is changed to the highest of them move up one place and the rest move down to be a 1010..10 pattern at the low end.
1111100111000000
->
1111101000001010
^ ^ ^
up endThe final value in a 2*w block is all 1s at the top and 0s at the bottom. It extends and becomes alternating 1010..10 as the first of the next bigger block. For example
111000 last 6-bit value
->
10101010 first 8-bit valueIth
As described above there are Catalan(w) many values with 2*w bits. The width of the i'th can be found by successively subtracting C(1), C(2), etc until reaching a remainder i < C(w), giving width 2*w with w many "1"s and w many "0"s.
After outputting some bits there will be some number z many "0"s and n many "1"s yet to be output. The choice is then to output either 0 or 1 and reduce z or n accordingly.
numvalues(z,n) = number of sequences of z "0"s and n "1"s
with remaining 0s never less than remaining 1s
output
0 if i < numvalues(z-1,n)
1 if i >= numvalues(z-1,n)
and subtract numvalues(z-1,n)
which are the "0..." combinations skippedThe numvalues() table can be constructed by
for z=1 upwards
numvalues(z,0) = 1
for n = 1 to z
numvalues(z,n) = numvalues(z-1,n) # the 0... forms
+ numvalues(z,n-1) # the 1... formsEach numvalues(z,n-1) is just the previous value calculated, so
for z=1 upwards
t = numvalues(z,0) = 1
for n = 1 to z
t += numvalues(z-1,n)
numvalues(z,n) = tThe last entry numvalues(w,w) in each row is Catalan(w), so can be used for the initial i subtractions seeking the width w. If building or extending a table each time then stop the table at that point.
Catalan(w) grows as a power a little less than 4^w so the table has roughly log4(i) many rows.
SEE ALSO
Math::NumSeq, Math::NumSeq::Catalan, Math::NumSeq::Fibbinary
HOME PAGE
http://user42.tuxfamily.org/math-numseq/index.html
LICENSE
Copyright 2012 Kevin Ryde
Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.