生成汉明距离 t 内的所有位序列 [英] Generate all sequences of bits within Hamming distance t

问题描述

给定一个比特向量v，计算具有v的汉明距离为1的比特集合，then，距离为2，向上到输入参数 t.

Given a vector of bits v, compute the collection of bits that have Hamming distance 1 with v, then with distance 2, up to an input parameter 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.这将在我的实际代码中运行很多次，因此也欢迎提高效率(即使支付更多内存).

How to efficiently compute this? The vector won't be always of dimension 3, e.g. it could be 6. This will run numerous time in my real code, so some efficiency would be welcome as well (even by paying more memory).

我的尝试:

#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
", 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
", str);
        size_t len = strlen(str);
        size_t maxDistance = len;
        for (size_t i = 1 ; i <= maxDistance ; ++i) {
                printf("Computing for distance %d
", i);
                magic(str, len-1, i);
                printf("----------------
");
        }
        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 内的所有位序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！