0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Have you already googled for "Hamming distance"? $\endgroup$ – Wolfgang Dec 10 '15 at 10:51
  • $\begingroup$ 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. $\endgroup$ – user83929 Dec 10 '15 at 11:05
  • $\begingroup$ 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. $\endgroup$ – Pushpendre Dec 10 '15 at 17:19
1
$\begingroup$

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.

One can find tables for maximum size of such sets in question. For example see here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, that should put me on the right track. I don't really need the set to have the largest possible size, just a size that is "large enough". Still need to figure out a way of computing said set though... $\endgroup$ – user83929 Dec 10 '15 at 15:50
  • $\begingroup$ the answer heavily depends on what $n$, minimum distance, and alphabet size you're interested in. $\endgroup$ – kodlu Dec 10 '15 at 21:10
  • $\begingroup$ As per requirements of my real world problem, n=8, d=6. I have "freedom" on the size of the alphabets (how many alternative questions I write) but obviously I'd like to write as few as possible while still being able to produce coursework for around 200 students. $\endgroup$ – user83929 Dec 11 '15 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.