生成汉明距离 t 内的所有比特序列
Generate all sequences of bits within Hamming distance t
给定一个位向量 v
,计算汉明距离为 1 且 v
、然后 距离为 2 的位集合,直到输入参数 t
.
所以
011 I should get
~~~
111
001
010
~~~ -> 3 choose 1 in number
101
000
110
~~~ -> 3 choose 2
100
~~~ -> 3 choose 3
如何有效地计算这个?矢量并不总是 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 位向量和基数 k(具有更改位的索引集)的子集(n 又名 v.size()
)之间存在双射。因此,我将改为枚举已更改索引的子集。快速浏览 SO 历史记录显示 this 参考。当然,您必须跟踪正确的基数。
考虑效率可能毫无意义,因为无论如何解决问题的方法都是指数级的。
如果汉明距离 h(u, v) = k
,则 u^v
恰好设置了 k
位。换句话说,在设置了 k
位的所有掩码 m
上计算 u ^ m
会给出具有所需汉明距离的所有单词。请注意,此类掩码集不依赖于 u
.
也就是说,对于 n
和 t
相当小的掩码集,预先计算设置了 k
位的掩码集,对于 1,t
中的所有 k
,并根据需要迭代这些集合。
如果您没有足够的内存,您可以即时生成 k 位模式。有关详细信息,请参阅 this discussion。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
void magic(char* str, int i, int changesLeft) {
if (changesLeft == 0) {
printf("%s\n", str);
return;
}
if (i < 0) return;
// flip current bit
str[i] = str[i] == '0' ? '1' : '0';
magic(str, i-1, changesLeft-1);
// or don't flip it (flip it again to undo)
str[i] = str[i] == '0' ? '1' : '0';
magic(str, i-1, changesLeft);
}
int main(void) {
char str[] = "011";
printf("%s\n", str);
size_t len = strlen(str);
size_t maxDistance = len;
for (size_t i = 1 ; i <= maxDistance ; ++i) {
printf("Computing for distance %d\n", i);
magic(str, len-1, i);
printf("----------------\n");
}
return 0;
}
输出:
MacBook-Pro:hammingDist gsamaras$ nano kastrinis.cpp
MacBook-Pro:hammingDist gsamaras$ g++ -Wall kastrinis.cpp
MacBook-Pro:hammingDist gsamaras$ ./a.out
011
Computing for distance 1
010
001
111
----------------
Computing for distance 2
000
110
101
----------------
Computing for distance 3
100
----------------
针对 Kastrinis 的回答,我想验证这是否可以扩展到我的基础示例,如下所示:
#include <iostream>
#include <vector>
void print(std::vector<char>&v)
{
for (auto i = v.begin(); i != v.end(); ++i)
std::cout << (int)*i;
std::cout << "\n";
}
void magic(std::vector<char>& str, const int i, const int changesLeft) {
if (changesLeft == 0) {
print(str);
return;
}
if (i < 0) return;
// flip current bit
str[i] ^= 1;
magic(str, i-1, changesLeft-1);
// or don't flip it (flip it again to undo)
str[i] ^= 1;
magic(str, i-1, changesLeft);
}
int main(void) {
std::vector<char> str = {0, 1, 1};
print(str);
size_t len = str.size();
size_t maxDistance = str.size();
for (size_t i = 1 ; i <= maxDistance ; ++i) {
printf("Computing for distance %lu\n", i);
magic(str, len-1, i);
printf("----------------\n");
}
return 0;
}
输出相同。
PS - 我也是.
给定一个位向量 v
,计算汉明距离为 1 且 v
、然后 距离为 2 的位集合,直到输入参数 t
.
所以
011 I should get
~~~
111
001
010
~~~ -> 3 choose 1 in number
101
000
110
~~~ -> 3 choose 2
100
~~~ -> 3 choose 3
如何有效地计算这个?矢量并不总是 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 位向量和基数 k(具有更改位的索引集)的子集(n 又名 v.size()
)之间存在双射。因此,我将改为枚举已更改索引的子集。快速浏览 SO 历史记录显示 this 参考。当然,您必须跟踪正确的基数。
考虑效率可能毫无意义,因为无论如何解决问题的方法都是指数级的。
如果汉明距离 h(u, v) = k
,则 u^v
恰好设置了 k
位。换句话说,在设置了 k
位的所有掩码 m
上计算 u ^ m
会给出具有所需汉明距离的所有单词。请注意,此类掩码集不依赖于 u
.
也就是说,对于 n
和 t
相当小的掩码集,预先计算设置了 k
位的掩码集,对于 1,t
中的所有 k
,并根据需要迭代这些集合。
如果您没有足够的内存,您可以即时生成 k 位模式。有关详细信息,请参阅 this discussion。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
void magic(char* str, int i, int changesLeft) {
if (changesLeft == 0) {
printf("%s\n", str);
return;
}
if (i < 0) return;
// flip current bit
str[i] = str[i] == '0' ? '1' : '0';
magic(str, i-1, changesLeft-1);
// or don't flip it (flip it again to undo)
str[i] = str[i] == '0' ? '1' : '0';
magic(str, i-1, changesLeft);
}
int main(void) {
char str[] = "011";
printf("%s\n", str);
size_t len = strlen(str);
size_t maxDistance = len;
for (size_t i = 1 ; i <= maxDistance ; ++i) {
printf("Computing for distance %d\n", i);
magic(str, len-1, i);
printf("----------------\n");
}
return 0;
}
输出:
MacBook-Pro:hammingDist gsamaras$ nano kastrinis.cpp
MacBook-Pro:hammingDist gsamaras$ g++ -Wall kastrinis.cpp
MacBook-Pro:hammingDist gsamaras$ ./a.out
011
Computing for distance 1
010
001
111
----------------
Computing for distance 2
000
110
101
----------------
Computing for distance 3
100
----------------
针对 Kastrinis 的回答,我想验证这是否可以扩展到我的基础示例,如下所示:
#include <iostream>
#include <vector>
void print(std::vector<char>&v)
{
for (auto i = v.begin(); i != v.end(); ++i)
std::cout << (int)*i;
std::cout << "\n";
}
void magic(std::vector<char>& str, const int i, const int changesLeft) {
if (changesLeft == 0) {
print(str);
return;
}
if (i < 0) return;
// flip current bit
str[i] ^= 1;
magic(str, i-1, changesLeft-1);
// or don't flip it (flip it again to undo)
str[i] ^= 1;
magic(str, i-1, changesLeft);
}
int main(void) {
std::vector<char> str = {0, 1, 1};
print(str);
size_t len = str.size();
size_t maxDistance = str.size();
for (size_t i = 1 ; i <= maxDistance ; ++i) {
printf("Computing for distance %lu\n", i);
magic(str, len-1, i);
printf("----------------\n");
}
return 0;
}
输出相同。
PS - 我也是