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

Sun Oct 18 17:53:31 CEST 2009

I don't have much time, so I will reply without understanding whether
it is a coincidence that for
START = [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1]
and END = [1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0],
B(START) is the bitwise inverse of END (and reciprocally...)

Starting out from START and doing
A2, B, A3, B, A11, B, A4, B
I got  B( START ).

So I tried
B(START) , A"-2", B, A"-3", B, A2 (=A"-11"), B, A"-4", B
which indeed gives B.
(in the above, A"-k" means to do A[n+1-k] where n is the length of the string).

The idea which led to the solution was to produce the required run lengths.

But I don't know if this would always work.
(I think this is interesting ; if it is possible to construct two
strings that cannnot be transformed one into the other, then it should
be possible to define some "invariant" which remains constant under
the two transformations (or at least under A[k] o B ) and which would
allow to know when S1 cannot be transformed into S2.)
Unfortunately I don't have the time to think further about this today.

Maximilian

A(x,b)={ b<0 & b=#x+1+b; x[b]=!x[b]; x }
B(x, L=[1], S)={ for( i=2,#x, x[i]==x[i-1] & L[#L]++ & next;
L=concat(L,1)); S=Set(L);
x=!x[1]; concat( vector( #L, i, x=!x; vector( eval(S[#S+1-setsearch(
S, L[i] )]), j, x ))) }

On Sun, Oct 18, 2009 at 10:26 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
> 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/
>>
>
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>