给定一个位向量v，计算汉明距离为1 v， 然后 为距离2直至输入参数的位集合t。
v
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 ----------------
