Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #64611

generate De Bruijn sequence memory and string vs lists

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

For reference, Wikipedia entry for De Bruijn sequence
http://en.wikipedia.org/wiki/De_Bruijn_sequence

At the above link is a python algorithm for generating De Brujin sequences.
It works fine but outputs a list of integers [0, 0, 0, 1, 0, 1, 1, 1] and I
would prefer a string '00010111'. This can be accomplished by changing the
last line from;
return sequence
to
return ''.join([str(i) for i in sequence])
See de_bruijn_1 Below.

The other option would be to manipulate strings directly (kind of).
I butchered the original algorithm to do this. See de_bruijn_2 below. But
it is much slower and ungly.

I am wanting to make a few large De Bruijin sequences. hopefully on the
order of de_bruijn(4, 50) to de_bruijn(4, 100) (wishful thinking?). I don't
know the limits (memory or time) for the current algorithms. I think I am
will hit the memory mazsize limit at about 4^31. The system I will be using
has 64GB RAM.
The size of a De Brujin sequence is k^n

My questions;
1, de_bruijn_2 is ugly, any suggestions to do it better?
2, de_bruijn_2 is significantly slower than de_bruijn_1. Speedups?
3, Any thought on which is more memory efficient during computation.

#### 1 ####
def de_bruijn_1(k, n):
    """
    De Bruijn sequence for alphabet size k (0,1,2...k-1)
    and subsequences of length n.
    From wikipedia Sep 22 2013
    """
    a = [0] * k * n
    sequence = []
    def db(t, p,):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(int(a[t - p]) + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    #return sequence  #original
    return ''.join([str(i) for i in sequence])

d1 = de_bruijn_1(4, 8)

#### 2 ####
def de_bruijn_2(k, n):
    global sequence
    a = '0' * k * n
    sequence = ''
    def db(t, p):
        global sequence
        global a
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence = sequence + a[j]
        else:
            a = a[:t] + a[t - p]  + a[t+1:]
            db(t + 1, p)
            for j in range(int(a[t - p]) + 1, k):
                a = a[:t] + str(j)  + a[t+1:]
                db(t + 1, t)
        return sequence
    db(1, 1)
    return sequence

d2 = de_bruijn_2(4, 8)


Vincent Davis

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

generate De Bruijn sequence memory and string vs lists Vincent Davis <vincent@vincentdavis.net> - 2014-01-23 08:23 -0600

csiph-web