# Finding maximal sets of words at minimum distance

Given an alphabet $Q$ with $k$ letters, consider the set $W(n, k)$ of all words in $Q$ with exactly $n$ letters.

In $W(n, k)$ we can define a distance by $dist(x,y) = \#\{ \text{Places where$x$and$y$differ}\}$

I am interested in obtaining a set of words $S$, as big as possible, such that for each two words $x, y \in S$ one has $dist(x, y) >= c$ for some specific value of $c$. I have two questions about it:

1. Is there a closed formula for the maximum possible size of such a set?
2. Is there an algorithm (apart from randomized search) that provides a maximal set, or at least a reasonable approximation?

I have already tried randomized search and the results are very poor, for example in 4-letter words in two symbols it never finds more than 3 or 4 words in the set, but I managed to show there is a set with 8.

In case you are wondering, this comes from a real world "problem":

I am trying to design randomized coursework/exams for my students. I have 8 topics I want to ask them about, and I can write multiple questions for each topic. I want to give each one of them a different assignment, but making sure that no two assignments have more than two repeated questions; i.e. I want words of length 8, at a minimum distance of 6 from each other. My problem is finding out how many different options I have to write for each question so that I have enough assignments, and then finding out an adequate set of words which is at least as big as whatever the size of the class I have!

• Have you already googled for "Hamming distance"? Dec 10 '15 at 10:51
• Yes. Didn't find any resources that took me any closer to an answer, but I am not a combinatorialist nor a code-theorist, so maybe I am looking in the wrong place? If this (constructing the maximal set) is a known algorithm I'd be happy just getting the name. Dec 10 '15 at 11:05
• this a response to the real word question. for a binary alphabet the number of words of length $2n$ at a distance of k are equal to the number of words at distance of $2n-k$. finding words at edit distance of two is easy enough. there is python code by peter norvig that does it. Dec 10 '15 at 17:19

Finding the largest possible set of words of length $n$ over a given alphabet with a specified minimum distance is in general a hard problem. In terms of coding theory the minimum distance determines the number of errors which can be corrected/detected.
The size of the set $S$ in question is bounded between the Hamming bound and the Gilbert–Varshamov bound. When these bounds (or some other upper and lower bounds) match we get the maximal size of such and $S$. Otherwise one has to search for a set size between the known bounds.
• the answer heavily depends on what $n$, minimum distance, and alphabet size you're interested in. Dec 10 '15 at 21:10