3
$\begingroup$

Let's represent integers with D digits where each digit has B values (i.e., the base is B and we effectively work only with integers between 1 and B^D). Is it possible to choose a single cyclic/repeating stream of B^D digits and D relative position "windows" (to look into that stream and filter out the digits we view) such that all integers come out?

As an example, for D=3 and B=3, the stream "1 2 1 2 3 3 1 1 2 3 1 1 3 2 3 2 1 2 2 2 1 2 1 3 3 3 3" with window positions at "1 11 18" generates the full range of integers exactly once per cycle (the first integer generated is 112, then 212, ...).

I'm actually looking for an answer for D=4 and B=4 if there is no general method.

Improve this question
$\endgroup$
6
  • $\begingroup$ This might be confusing because my digits in the example ranged from 1 to 3. It's more normal to use a range from 0 to 2, so subtract one from all digits if that makes it more intuitive. $\endgroup$
    – bobuhito
    Commented Apr 29, 2014 at 16:40
  • 2
    $\begingroup$ You might be interested in DeBruijn cycles and adaptations. In Debruijn cycles, the window is continguous of length D. Finding a permutation which preserves the DeBruijn property but changes the window might be of interest. Gerhard "Then Again, It Might Not" Paseman, 2014.04.29 $\endgroup$
    – Gerhard Paseman
    Commented Apr 29, 2014 at 18:25
  • 1
    $\begingroup$ I didn't know about DeBruijin. The answer is therefore yes, and, even more amazing, a contiguous window can always be used. So, that begs the question, can a stream be found for any given window? By your comment, I guess you extended my question to this already. Thanks. $\endgroup$
    – bobuhito
    Commented Apr 29, 2014 at 18:48
  • $\begingroup$ Try writing the digits in a circle. If there are 4n many digits, try swapping every other diametrically opposed pair with itself. This suggests an alternate cycle which switches the window elements around. Gerhard "Likes To Mix Things Up" Paseman, 2014.04.29 $\endgroup$
    – Gerhard Paseman
    Commented Apr 29, 2014 at 19:00
  • $\begingroup$ @bobuhito, When you say "all integers come out", do you just mean that you will get all $B^D$ integers of length $D$? I'm sure you must mean this, but I just want to check that I understand your question properly. $\endgroup$
    – Nick Gill
    Commented Apr 30, 2014 at 15:27

2 Answers 2

Reset to default
1
$\begingroup$

Yes. @GerhardPaseman's comment about De Bruijn cycles points to the solution:

a $k$-ary De Bruijn sequence $B(k, n)$ of order $n$ is a cyclic sequence of a given alphabet $A$ with size $k$ for which every possible subsequence of length $n$ in $A$ appears as a sequence of consecutive characters exactly once.

Now the result you require follows from the fact that

De Bruijn sequences of all orders exist.

The relevant reference is:

van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), Circuits and trees in oriented linear graphs, Simon Stevin 28: 203--217.

The special case $k=2$ was first proved here:

Flye Sainte-Marie, C. (1894), Solution to question nr. 48, L'intermédiaire des Mathématiciens 1: 107--110.

More details here (including the intriguing tidbit that "the earliest known example of a De Bruijn sequence comes from Sanskrit prosody"; make of that what you will).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I must be missing something, but how does the existence of DeBruijn cycles of all sizes imply the corresponding result for windows with non-consecutive positions? $\endgroup$
    – ARupinski
    Commented May 2, 2014 at 19:22
  • $\begingroup$ @ARupinski the window is free to choose, so choose one with consecutive positions. $\endgroup$
    – hobbs
    Commented May 2, 2014 at 19:24
  • $\begingroup$ I was referring to the interesting variation in which the window is predetermined and one looks for a generalized DeBruijn sequence with respect to the chosen window; it seems that none of the standard literature on DeBruijn sequences modifies easily to that case (although im also having a difficult time constructing a counterexample). $\endgroup$
    – ARupinski
    Commented May 2, 2014 at 19:33
  • $\begingroup$ @ARupinski, You're quite right. I hadn't read through all the earlier comments and I haven't addressed the extra (interesting) question. I don't know how to address it directly. $\endgroup$
    – Nick Gill
    Commented May 2, 2014 at 21:03
0
$\begingroup$

The more generalized problem (given window positions, and alphabet size, find a cyclic or even non cyclic zequence such that shifting window positions gives all words of length same as concatenated window) sounds like a recurrence problem to me. For window length of 2 with position difference k coprime to the alphabet size and possibly to 2, one can write the DeBruijin cycle in skip digit fashion. So for window positions 1 and 4 and alphabet size coprime to 3 start filling in positions 1,4,7,10,13,... with consecutive members of the DeBruijn string. Also one might check out gray coding systems to see if any resemble what bobuhito wants.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .