in reply to (OT) A different kind of 'combinatorics'

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.

Replies are listed 'Best First'.
Re^2: (OT) A different kind of 'combinatorics'
by BrowserUk (Patriarch) on Mar 26, 2015 at 15:51 UTC
    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
[reply]
[d/l]
Re^2: (OT) A different kind of 'combinatorics'
by Anonymous Monk on Apr 20, 2017 at 13:48 UTC
[reply]
[d/l]

      That was me.

[reply]

In Section Seekers of Perl Wisdom