生成漢明距離t

Question

鑑於比特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 

Answer 1

#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 
---------------- 

Answer 2

首先：有kardinality k的漢明DIST k個位向量和子集之間的雙射（正的又名v.size()） （具有改變位的一組索引）。因此，我會列舉改變索引的子集。快速瀏覽SO歷史顯示this參考。當然，你必須跟蹤正確的核心。

考慮到效率可能是毫無意義的，因爲您的問題的解決方案無論如何都是指數級的。

Answer 3

如果漢明距離h(u, v) = k，那麼u^v正好設置了k位。換句話說，在所有掩碼m上計算u^m而使用k位集給出具有期望的漢明距離的所有字。請注意，這類掩碼不取決於u。

也就是說，n和t相當小的，預先計算的套面具與k位設置，在1,t所有k，並根據需要遍歷這些集合。

如果您沒有足夠的內存，您可以即時生成k位模式。有關詳細信息，請參見this discussion。

Answer 4

針對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 - 我也toggling the bit with a different way。}