It seems that De Bruijn sequences are what you are searching for. Wikipedia even lists an algorithm, albeit in Python.

Update: As I assume that this is somewhat related to your quest of finding a misaligned sequence, you might be interested in the section "De Bruijn decoding", which hints at specially constructed sequences that can be mapped back to the position/offset in O(n log(n)) if you can't use a lookup table to convert the sequence value back to an offset.

It seems that De Bruijn sequences are what you are searching for.

Yes. Thankyou!

As I assume that this is somewhat related to your quest of finding a misaligned sequence, you might be interested in the section "De Bruijn decoding", which hints at specially constructed sequences that can be mapped back to the position/offset in O(n log(n)) if you can't use a lookup table to convert the sequence value back to an offset.

Yes. I'm looking for a testing strategy to ensure that all patterns that can be found are.

And the "De Bruijn decoding" looks very interesting. Thanks again.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

length unspecified

It is easy to see that the length must be equal to $number_of_patters + $size_of_pattern - 1 as a new pattern is introduced at every bit offset.

It is easy to see that the length must be equal to $number_of_patters + $size_of_pattern - 1 as a new pattern is introduced at every bit offset.

Correct. I'd worked out that for 4, 19 had to be the minimum length, but I wasn't convinced that it could be done in the minimum length.

Now you've pointed it out, it is becomes obvious that it can only be done in the minimum length; else you'd have dups.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

If each set of four were to be repeated, it'd be impossible, because after 0000 or 1111 the next digit must be either 0 or 1, which will be a repeat of 0000, 1111, 0001 or 1110. So, the question would only be valid for a condensed string that happens to includes all combinations but not more than once. (This is probably what you are asking, but i did not see it so clearly at first.)

If each set of four were to be repeated, it'd be impossible ... This is probably what you are asking, but i did not see it so clearly at first.

Indeed, though it wasn't obvious to me at first either.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

I have now no time to code but this is what I would do. My usual approach is to do gradually build it up recursively with backtracking. I would think that you would not see many of the 16! possible combinations in such a procedure. If one would use a string as the underlying data structure, then a regex should be possible to identify the bad patterns. My first thought was m/(....).*\1/ but that would not detect overlapping repetitions. But I am sure such a regex exists.

My first thought was m/(....).*\1/ but that would not detect overlapping repetitions. But I am sure such a regex exists.

I was looking to combine lookaheads with captures to check for dups, but then settled for using index to check for existance, and again, with the offset+1 from the first to check for duplicates.

My brute forcer finds 208 complient patterns in about a minute:

#! perl -slw
use strict;
use List::Util qw[ shuffle ];
use Algorithm::Combinatorics qw[ combinations permutations];

our $N //= 4; my $Nth2 = 1 << $N;

my @pats = map sprintf( "%0${N}b", $_ ), 0 .. $Nth2 -1;

my $p;
OUTER: for my $i ( 1 << $Nth2 -1 .. 2**( $Nth2 + $N -1 ) - ( 2**$Nth2 
+)-1 ) {
    my $b = sprintf "%0${ \( $Nth2 + $N -1 ) }b", $i;
    printf "\r$b\t";
    for my $pat ( @pats ) {
        #print( " missing $pat" ),
        next OUTER unless $p = 1+index $b, $pat;
        #print( " duplicate $pat" ),
        next OUTER if 1+index $b, $pat, $p;
    }
    for my $i ( 0 .. length( $b ) - $N ) {
        my $sub = substr $b, $i, $N;
        for my $j ( 0 .. $#pats ) {
             printf "%u ", $j if $sub eq $pats[ $j ];
        }
    }
    print "\tGot one";
}
[download]

The second set of numbers is the order of the 4-bit patterns within the 19-bit solutions -- in the vague hope they might give some hint as to a generic algorithm -- now rendered unnecessary as Corion's discovered it is a solved problem.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

And the regex is:

m/(?=(....)).+\1/
[download]

That was me.