Генерировать все последовательности битов в пределах расстояния Хэмминга т

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

Во-первых: Существует взаимно однозначное соответствие между Хэмминга расстояние K битовых векторов и подмножеств (п ака v.size()) из kardinality к (набор индексов с измененными битами). Следовательно, я бы перечислил подмножества измененных индексов. Быстрый взгляд на историю SO показывает this ссылка. Конечно, вам нужно будет следить за правильными кардиналами.

Учитывая эффективность, возможно, бессмысленно, так как решение вашей проблемы в любом случае экспоненциально.

Answer 3

Если Хемминг расстояние h(u, v) = k, то u^v имеет точно k бит. Другими словами, вычисление u^m по всем маскам m с набором k бит дает все слова с желаемым расстоянием Хэмминга. Обратите внимание, что такой набор маски не зависит от u.

То есть, для n и t достаточно маленьких, предвычислений наборов масок с k бит установлена, для всех k в 1,t и перебирать эти наборы по мере необходимости.

Если у вас недостаточно памяти, вы можете генерировать 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.}