# Sequence Generation with Combinations and Permutations

I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:

nucleotides = ['A','C','G','T']


From this, I'd like to generate as many sequences as possible of 10 nucleotides long, e.g.

ACGCTATACA
ACGCATCTAA
...


On condition that all sequences in the set have at least 5 or more nucleotides in the same character position different. In the previous example, the positions 5,6,7,8,9 (TATAC vs ATCTA) are different giving it a distance of 5 satisfying our criteria.

For sequences of 4 bases, the following set satisfies a distance of at least 3 (No pair of sequences has more than one common same-position nucleotide):

    ACGT
CATG
GTAC
TGCA
GCTA
TAGC
ATCG
CGAT
TCAG
GACT
CTGA
AGTC
AAAA
CCCC
GGGG
TTTT


The problem relates to the Kirkman's Schoolgirl Problem.

The problem could be solved computationally by generating sequencing one-by-one whilst verifying the condition at every step. I am curious if there is a mathematical approach.

How could I approach generating a set for 10 bases with a distance of at least 5? How can I generalise this to n bases and at least d distance?

According to this table an $(n,d)=(10,5)$ quaternary code can have at least $1024$ different strings but not more than $2045.$

An example giving the lower bound can likely be described simply using the field with $4$ elements.

The upper bound seems weak. There are $w=1048576$ words. For each one chosen there are $30$ which differ from it in exactly one place and $405$ in exactly two. $\frac{w}{436}=2404.99$ This does not yet account for words at distance $3$ or $4$ from one or more chosen ones.