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!

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you already googled for "Hamming distance"? $\endgroup$
    – Wolfgang
    Commented Dec 10, 2015 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
    Commented Dec 10, 2015 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
    Commented Dec 10, 2015 at 17:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Dec 10, 2015 at 15:50
  • $\begingroup$ the answer heavily depends on what $n$, minimum distance, and alphabet size you're interested in. $\endgroup$
    – kodlu
    Commented Dec 10, 2015 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
    Commented Dec 11, 2015 at 10:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .