还是回溯法.
预计算两两之间的汉明距离，以及用一个forbidden数组记录不可用的数，可以优化一下计算。
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("hamming.in");
ofstream fout("hamming.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
//两两之间距离
int dist[1<<8][1<<8];
int n,b,d;
//最大的数
int largest;
int forbidden[1<<8];
//用来保存一个forbidden数组
int tmp[1<<8];
//保存解
int result[64];
//计算n中的1的个数
int count_bit(int n)
{
int res = 0;
while(n!=0){
n&=(n-1);
res++;
}
return res;
}
//汉明距离为两者异或值的1的个数
int compute_dist(int i,int j)
{
return count_bit(i^j);
}
//将所有汉明距离小于d的数forbid掉
void add_code(int code)
{
forbidden[code]++;
for(int i=0;i<largest;++i){
if(dist[code][i]<d)
forbidden[i]++;
}
}
void output()
{
for(int i=0;i<n;++i){
if(i%10==0){
out<<result[i];
}else{
out<<" "<<result[i];
if(i%10==9)
out<<endl;
}
}
if(n%10!=0)
out<<endl;
}
void backtracing(int depth,int code)
{
if(forbidden[code]!=0) return;
result[depth]=code;
if(depth==n-1){
output();
exit(0);
}
memcpy(tmp,forbidden,sizeof(int)*n);
add_code(code);
for(int i=0;i<largest;++i){
if(forbidden[i]==0&&dist[i][code]>=d){
backtracing(depth+1,i);
}
}
memcpy(forbidden,tmp,sizeof(int)*n);
}
void solve()
{
in>>n>>b>>d;
largest = (1<<b);
for(int i=0;i<largest;++i)
for(int j=i+1;j<largest;++j){
dist[i][j] = dist[j][i] = compute_dist(i,j);
}
backtracing(0,0);
}
int main(int argc,char *argv[])
{
solve();
return 0;
}