给定一个位 vector v
,用 v
计算汉明距离为 1 的位集合,然后 距离为 2,向上到输入参数t
。
所以对于
011 I should get
~~~
111
001
010
~~~ -> 3 choose 1 in number
101
000
110
~~~ -> 3 choose 2
100
~~~ -> 3 choose 3
如何有效地计算这个?该 vector 并不总是维度为 3,例如它可能是 6。这将在我的真实代码中运行很多次,因此也欢迎一些效率(即使付出更多的内存)。
我的尝试:
#include <iostream>
#include <vector>
void print(const std::vector<char>& v, const int idx, const char new_bit)
{
for(size_t i = 0; i < v.size(); ++i)
if(i != idx)
std::cout << (int)v[i] << " ";
else
std::cout << (int)new_bit << " ";
std::cout << std::endl;
}
void find_near_hamming_dist(const std::vector<char>& v, const int t)
{
// if t == 1
for(size_t i = 0; i < v.size(); ++i)
{
print(v, i, v[i] ^ 1);
}
// I would like to produce t == 2
// only after ALL the t == 1 results are reported
/* how to? */
}
int main()
{
std::vector<char> v = {0, 1, 1};
find_near_hamming_dist(v, 1);
return 0;
}
输出:
MacBook-Pro:hammingDist gsamaras$ g++ -Wall -std=c++0x hammingDist.cpp -o ham
MacBook-Pro:hammingDist gsamaras$ ./ham
1 1 1
0 0 1
0 1 0
最佳答案
首先:汉明分布 k 位 vector 和基数 k(具有更改位的索引集)的子集(n 又名 v.size()
)之间存在双射。因此,我将枚举更改索引的子集。快速浏览一下 SO 历史显示 this引用。当然,您必须跟踪正确的基数。
考虑效率可能毫无意义,因为问题的解决方案无论如何都是指数级的。
关于c++ - 生成汉明距离 t 内的所有比特序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40813022/