Fortnightly teaser De Bruin Sequence

[TorQ Guru]

Hi All,

The "Sieve teaser" posed previously will be closed up later in the week, but for now here is the next teaser in this series.

In combinatorial mathematics, a De Bruijn sequence (DBRN) of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as acontiguous subsequence). ( https://en.wikipedia.org/wiki/De_Bruijn_sequence )

In practical terms the sequence can be used to shorten a brute-force attack on a PIN-like code lock that does not have an "enter" key and accepts the last n digits entered. For example, a digital door lock with a 4-digit code and no enter key would require at most 10000 + 3 = 10003 (as the solutions are cyclic) presses to open the lock. Trying all codes separately would require 4 × 10000 = 40000 presses.

This task is asking you to create a function which will create any single  DBRN sequence of length n from the input list which can be assumed to be a list of unique characters. I.e. DBRN[n;l] and thus provide a sequence of key presses to guarantee opening the "simple" numeric lock described above.

eg DBRN[3;0 1]

00010111 or  11101000

Regards,

TorQ

[Matt Doherty]

Fun problem :-).  Well over 100 chars so not exactly concise, but the best I've come up with so far:

{y raze l where 0=mod[x] count each l:{r:_[-1]/[{x=last y}[x];y#z];(-1_r),1+last r}[c;x]\[{not y~(),x}[c:count[y]-1];0]}

Looking forward to seeing how others approach it!

Here's more or less the same answer in python if anyone's into that (everyone will be pleased to hear it's not as fast, probably all those characters slowing it down :-P):

def deBruijn(a,n):

    def nextLyndon(w, k, n):

        x = (w*n)[:n]

        while x[-1] == k-1: x = x[:-1]

        x[len(x)-1] += 1

        return x

    k = len(a);w = s = [0]

    while w != [k-1]:

        w = nextLyndon(w, k, n)

        if n % len(w) == 0: s += w

    return [a[i] for i in s]

Matt