生成汉明距离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

回答:

#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

----------------

以上是 生成汉明距离t内的所有位序列 的全部内容, 来源链接: utcz.com/qa/398433.html

回到顶部