Hamming Codes - USACO 2.1.5

hammingcodes - codetrick
Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):

        0x554 = 0101 0101 0100          0x234 = 0010 0011 0100  Bit differences: xxx  xx  

Since five bits were different, the Hamming distance is 5.

PROGRAM NAME: hamming

INPUT FORMAT

N, B, D on a single line

SAMPLE INPUT (file hamming.in)

16 7 3  

OUTPUT FORMAT

N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted as a base 2^B integer, would have the least value.

SAMPLE OUTPUT (file hamming.out)

0 7 25 30 42 45 51 52 75 76  82 85 97 102 120 127  

http://www.cuiyn.tk/?p=207

首先0是必定在里面的，因为要考虑答案值最小的要求。所以，只要按递增顺序搜索N个从1到2^B的数，然后与已找到的数判断距离是否大于D，输出即可。由于是按照递增顺序搜索的，在得到解后它肯定满足排序的要求。

输入N，B,D 表示，在 [0,2^B-1] 中找出最小的 N 个数，两两间的 hamming 距离大于等于 D。
分析：从 0 开始依次搜索下去，找到前 N 就输入。这么暴力居然也过了
判断Hamming距离:

int fun(int a, int b)
{
 int c = a^b;
 int count = 0;
 while(c>0){ 
  c&=(c-1); 
  count++; 
 }
 return count;
}

a^b代表异或运算，得到c之后只需求出c的二进制表示中1的个数即可。我们采用逐位判断的方法，使用与运算：相同位的两个数字都为1，则为1；若有一个不为1，则为0。c&(c-1)可以将c的低位1改为0。

 int N, B, D,count=1;
 cin >>N>>B>>D;
 for(int i = ans[count-1]+1;i<=maxn[B];i++)
 {
  bool flag = true;
  for(int j = 0; j<count; j++)
  {
   if(fun(i,ans[j]) < D)
   {
    flag = false;
    break;
   }
  }
  if(flag)
  {
   ans[count] = i;
   count++;
  }
  if(count == N)
   break;
 }
 int tot=0;
 for(int i = 0; i<=count-1; i++)
 {
  cout <<ans[i];
  tot++;
  if(tot == 10 || i == count-1)
  {
   cout <<endl;
   tot=0;
  }
  else
   cout <<' ';
 }

https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/hamming.java

	ArrayList<Integer> set = new ArrayList<Integer>(); set.add(0);
	for(int i = 1; i < N;i++)
	{
	for(int j = 0; j < (1 << B);j++)
	{
	boolean good = true;
	for(int k = 0; k < set.size();k++)
	{
	if(hd(set.get(k),j) < D)
	{
	good = false;
	break;
	}
	}
	if(good)
	{
	set.add(j);break;
	}
	}
	}

http://jackneus.com/programming-archives/hamming-codes/
https://github.com/wuhanyu/usaco/blob/master/src/cp2/s21/hamming.java
Read full article from hammingcodes - codetrick