[seqfan] Re: Switching Binary Digits And Runs Of Digits

[Leroy Quet]

Since there seems to be limited interest in this, I will ask a simple question -- or at least it must be simple, but I have been having a little trouble with it.

Can you, alternating the transforms below (and starting either with A or with B), convert:

010011000111
to its reflection
111000110010 ?

This should be relatively easy.

Thanks,
Leroy Quet


[ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] ) ]


--- On Sat, 10/17/09, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:

> From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>
> Subject: [seqfan]  Switching Binary Digits And Runs Of Digits
> To: seqfan at seqfan.eu
> Date: Saturday, October 17, 2009, 1:51 PM
> I posted the text below to sci.math.
> It isn't strictly about sequences (except finite binary
> sequences). But it is inspired by sequence A166166. (Maybe
> someone could up with a more concise way to express the idea
> of exchanging runs, which seems to me to be intuitively easy
> to understand, but difficult to express in words.)
> 
> Also I post this because it makes for a fun puzzle.
> 
> ----
> 
> Let's say we start with a binary string of finite length. I
> will use 0's and 1's for the characters in the string, but
> any two distinct symbols will do. (A string may begin with
> either a 0 or a 1.)
> 
> We then alternate between transformation A and
> transformation B of the string, starting with either A or B,
> and not ever following transformation A immediately with
> transformation A, and not ever following transformation B
> immediately with transformation B.
> 
> A: Either replace any 0 in the string with a 1, or replace
> any 1 in the string with a 0. In other words, flip exactly
> one digit.
> 
> B: (More difficult to describe.) Rewrite the string with
> each run (of either digit b) of the kth-longest distinct
> run-length replaced with a run of digit b of a length equal
> to that of the k-th shortest distinct run-length, where k is
> any integer between 1 and the number of distinct
> run-lengths. In other words, let b(k) be the kth largest
> distinct run-length (considering both runs of 0's and of
> 1's) in the string yet to be transformed in this step. Let r
> be the number of distinct run-lengths in the string. Rewrite
> the string by replacing each run (of any given digit) of
> length b(k) with a run (of that same digit) of length
> b(r+1-k). 
> (A binary string alternates between "runs" each completely
> of 1's and runs completely of 0's. No two runs of the same
> digit are consecutive.)
> 
> (An example for transformation B: Let us say we have the
> string 0010000110. So, there is a run of length 2, followed
> by a run of length 1, followed by a run of length 4,
> followed by a run of length 2, followed finally by a run of
> length 1. The run-lengths are therefore (2,1,4,2,1). The
> distinct run lengths, written in order, are therefore
> (1,2,4).
> So, we replace all runs of length 1 with runs (of the same
> digit ) of length 4, because 1 is the smallest run-length,
> and 4 is the greatest run-length. Then we replace all runs
> of length 2 with runs of length 2 (leaving those runs
> unchanged), because 2 is both the 2nd longest run-length and
> the second shortest. And finally, we replace all runs of
> length 4 with runs of length 1.
> And we get:
> 0011110110000.)
> 
> The first question: Is it always possible to transform,
> through a series of such steps, any string of 4 or more
> digits to any other string of 4 or more digits?
> (I don't know the answer to this question.)
> 
> Now, let us say we have the relatively short string:
> 010011.
> 
> We can "reverse" the order of the digits easily either by
> starting with transformation A or with transformation B.
> 
> Start:: 010011
> B: 001101
> A: 001100
> B: 001100
> A: 101100
> B: 110010
> 
> Or:
> 
> Start: 010011
> A: 110011
> B: 110011
> A: 110010
> 
> Simple stuff.
> 
> But what if we have a string of n(n+1) digits, made by:
> One 0, followed by one 1, followed by two 0's, followed by
> two 1's, followed by three 0's, followed by three 1's,...
> followed by n 0's, followed finally by n 1's?
> 
> Is there a simple algorithm that "reverses" the order of
> the digits that works for all n >= 1?
> 
> (I don't know the answer to this question. I don't even
> know if this is possible for all n.)
> 
> It should be noted -- although this is obvious if you play
> with this -- that the binary string can alter in length
> whenever transformation B is applied.
> In regards to this and the first question, a
> clarification:  The starting string and the target
> string can be of different lengths, as long as both the
> start and the finish both have 4 or more digits. (At least 4
> digits are necessary because strings of length 3 only
> produce strings of length 3; and strings of length 2 produce
> only strings of length 2, and strings of length 1 produce
> only strings of length 1 -- so you cannot transform a string
> of 3 digits, say, to an arbitrary string of any other
> length.)
> 
> 
> Thanks,
> Leroy Quet
> 
>  
> [ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] )
> ]
> 
> 
>       
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
>