c++ - Generate all sequences of bits within Hamming distance t

Question

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.

So for

011  I should get
~~~ 
111
001
010
~~~ -> 3 choose 1 in number
101
000
110
~~~ -> 3 choose 2
100
~~~ -> 3 choose 3

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).

---

My attempt:

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

Output:

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

First: There is a bijection between hamming dist k bit-vectors and subsets (of n aka v.size()) of kardinality k (the set of indices with changed bits). Hence, I'd enumerate the subsets of changed indices instead. A quick glance at the SO history shows this reference. You'd have to keep track of the correct cardinalitites of course.

Considering efficiency is probably pointless, since the solution to your problem is exponential anyways.