Generate a sequence with unique subsequences

Question

The string 2123132133 has the property that no subsequence of length 3 is the same as any other subsequence of length 3.

Your task is to build a program that will output as long of a string as possible that satisfies this property for sequences of length 9 with the characters from 1 to 9.

The source code of your program may not be longer than 16 kilobytes (16,384 bytes). The program that wins is the one that outputs the longest sequence of digits from 1 to 9 such that no subsequence of 9 digits is the same.

Answer 1

What I'm starting with here is a De Bruijn sequence. Stealing some reference code on the topic, here is my submission:

#!/usr/bin/env python

def de_bruijn(k, n):
    """ De Bruijn sequence for alphabet size k and subsequences of length n. """
    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(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

seq = de_bruijn(9, 9) # cyclic
seq = seq + seq[:8]   # extended to max 
print(''.join(map(lambda n: chr(49+n), seq)))

After running for ten minutes, the output is a 387,420,497 digit sequence. This is 9^9 + 8 digits, as expected. (Thank you @PeterTaylor for the +8 tip on the cyclic output.)