<p>In general this is an open problem, so you should not expect anything like a clean formula or an algorithm. For linear codes (at least) an awful lot is known. The authors of</p>

<p><a href="http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html" rel="nofollow">http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html</a></p>

<p>maintain a database of everything(?) that is known about this problem (lower bounds, upper bounds, constructions).</p>

CC BY-SA 3.0
2012-09-06T19:32:54.177Z
2012-09-06T19:32:54.177Z
Jyrki Lahtonen
<p>Try the following command on MATLAB, as you're looking for a practical solution</p>

<pre><code>squareform(pdist(dec2bin(0:255,8),'hamming')*8)
</code></pre>

<p>It gives you a matrix, containing the pairwise hamming distance between binary numbers from 0 to 255.
You can plot it using any tool in matlab, such as 'imtool'. But be careful about the 1-based indexing of matrices in MATLAB!</p>

CC BY-SA 3.0
2012-10-07T11:40:01.940Z
2012-10-07T11:40:01.940Z
Nima.S
<p>In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.</p>

CC BY-SA 3.0
2012-06-13T20:59:39.833Z
2012-06-13T20:59:39.833Z
Mahdi Cheraghchi
<p>For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D. 
(The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)</p>

<p>Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?</p>

<p>Thank you very much.</p>

CC BY-SA 3.0
2012-06-13T09:36:56.663Z
Isn't the variation just asking for MDS code?
Yonatan
CC BY-SA 3.0
2012-06-13T12:13:52.287Z
As Yonatan hinted, please check the theory of error correcting codes.  There are many results about your question.  I cannot see a particular connection to MDS codes, though.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-13T12:50:05.010Z
can you please be bothered to state a relevant one "of the many results about my question"? i could not find one, which is why i am asking in this forum.
Chris K
CC BY-SA 3.0
2012-06-13T14:21:28.213Z
See http://en.wikipedia.org/wiki/Singleton_bound and references therein
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-13T15:46:27.280Z
I think that this should be an answer. It's a valid question and a clear answer.
Suresh Venkat
CC BY-SA 3.0
2012-06-13T18:30:23.067Z
@Suresh: Feel free to post an answer if you want to.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-13T18:49:13.603Z
Well it's your answer, not mine :)
Suresh Venkat
CC BY-SA 3.0
2012-09-07T14:51:50.027Z
You can find a few implementations if you Google for "hamming usaco" (https://www.google.co.uk/search?q=hamming+usaco). (It is one of the training problems for the USA Computing Olympiad.)
Radu GRIGore
<ds.algorithms><co.combinatorics><coding-theory>
Maximum subset of words with Hamming distance ≥ D
Chris K
# Maximum subset of words with Hamming distance ≥ D

(Asked by: username_0 on 2012-06-13)

For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D.
(The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)

Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?

Thank you very much.

**Tags:** ds.algorithms, co.combinatorics, coding-theory
> **Comments:**
> **username_1**: Isn't the variation just asking for MDS code?  
> **username_2**: As Yonatan hinted, please check the theory of error correcting codes.  There are many results about your question.  I cannot see a particular connection to MDS codes, though.  
> **username_0**: can you please be bothered to state a relevant one "of the many results about my question"? i could not find one, which is why i am asking in this forum.  
> **username_2**: See http://en.wikipedia.org/wiki/Singleton_bound and references therein  
> **username_3**: I think that this should be an answer. It's a valid question and a clear answer.  
> **username_2**: @Suresh: Feel free to post an answer if you want to.  
> **username_3**: Well it's your answer, not mine :)  
> **username_4**: You can find a few implementations if you Google for "hamming usaco" (https://www.google.co.uk/search?q=hamming+usaco). (It is one of the training problems for the USA Computing Olympiad.)  

---

## 3 answers

### Answer by username_7 on 2012-06-13. Score: 14 | Accepted answer

In coding theory, the quantity you are looking for is called $A\_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A\_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.


---

### Answer by username_5 on 2012-09-06. Score: 2

In general this is an open problem, so you should not expect anything like a clean formula or an algorithm. For linear codes (at least) an awful lot is known. The authors of

<http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html>

maintain a database of everything(?) that is known about this problem (lower bounds, upper bounds, constructions).


---

### Answer by username_6 on 2012-10-07. Score: -3

Try the following command on MATLAB, as you're looking for a practical solution
squareform(pdist(dec2bin(0:255,8),'hamming')*8)

It gives you a matrix, containing the pairwise hamming distance between binary numbers from 0 to 255.
You can plot it using any tool in matlab, such as 'imtool'. But be careful about the 1-based indexing of matrices in MATLAB!


---

