최대 입력 파라미터 <code>t</code>까지 거리 2 <em>다음</em>, <code>v</code>와 해밍 거리가 1이 비트의 컬렉션을 계산 비트 <code>v</code>의 벡터 주어 해밍 거리 t

Question

내의 모든 비트 시퀀스를 생성한다.

그래서

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; 
} 

출력 :

이 Kastrinis '대답에 대응

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의 (일명 N의 v.size()) 해밍 DIST K 비트 벡터와 서브 세트 사이의 전단 사 함수가있다 (변경된 비트를 갖는 인덱스 세트). 따라서 나는 대신 변경된 인덱스의 하위 집합을 나열합니다. SO의 역사를 간략하게 살펴보면 this 참고 자료입니다. 당연히 정확한 cardinalitites를 추적해야 할 것입니다.

문제를 해결할 수있는 솔루션이 기하 급수적이기 때문에 효율성을 고려하는 것은 무의미합니다.

Answer 3

해밍 거리가 h(u, v) = k 인 경우 u^v은 정확히 k 비트 집합을 갖습니다. 다시 말해, 모든 마스크에 대해 u^m을 계산하면 m이 k 비트로 설정되어 원하는 모든 해밍 거리를 갖는 모든 단어가 제공됩니다. 이러한 마스크 세트는 u에 의존하지 않습니다. k 비트 1,t 모든 k위한 설정하고 필요에 따라 이들 세트를 반복하여 마스크 및 nt 비교적 작은, 미리 계산 세트 들면

.

메모리가 충분하지 않은 경우 즉시 k 비트 패턴을 생성 할 수 있습니다. 자세한 내용은 this discussion을 참조하십시오.

Answer 4

, 나는이 같은이 내 기초 예제로 확장 될 수 있는지 확인하고 싶습니다 :

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

을 출력은 동일합니다.

---

_{추신 - 나는 또한 toggling the bit with a different way입니다.}