Erzeuge alle Bitfolgen innerhalb der Hamming-Distanz t

Gegeben ein Vektor von Bits v, berechne die Sammlung von Bits mit Hamming-Distanz 1 mit v, dann mit Abstand 2, bis zu einem Eingabeparameter t.

So für

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

Wie berechnet man das effizient? Der Vektor wird nicht immer die Dimension 3 haben, zB könnte er 6 sein. Dies wird in meinem echten Code viele Male ausgeführt, daher wäre auch eine gewisse Effizienz willkommen (auch wenn mehr Speicher bezahlt wird).

Mein Versuch:

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

Ausgabe:

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 

Erstens: Es gibt eine Bijektion zwischen Hamming-Dist-k-Bit-Vektoren und Teilmengen (von n aka v.size()) der Kardinalität k (der Satz von Indizes mit geänderten Bits). Daher würde ich stattdessen die Teilmengen der geänderten Indizes aufzählen. Ein kurzer Blick in die SO-Historie zeigt diese Referenz. Sie müssten natürlich die richtigen Kardinaliten im Auge behalten.

Auf Effizienz zu achten ist wahrscheinlich sinnlos, da die Lösung Ihres Problems sowieso exponentiell ist.

Wenn Hamming-Abstand h(u, v) = k, dann u^v hat genau k Bits gesetzt. Mit anderen Worten, rechnen u ^ m über alle Masken m mit k bits set liefert alle Wörter mit der gewünschten Hamming-Distanz. Beachten Sie, dass ein solcher Maskensatz nicht von abhängt u.

Das heißt, für n und t relativ kleine, vorberechnete Maskensätze mit k Bits gesetzt, für alle k in 1,t, und iterieren Sie diese Sätze nach Bedarf.

Wenn Sie nicht über genügend Speicher verfügen, können Sie die k-Bit-Muster im laufenden Betrieb generieren. Weitere Informationen finden Sie in dieser Diskussion.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

void magic(char* str, int i, int changesLeft) {
        if (changesLeft == 0) {
                printf("%sn", 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("%sn", str);
        size_t len = strlen(str);
        size_t maxDistance = len;
        for (size_t i = 1 ; i <= maxDistance ; ++i) {
                printf("Computing for distance %dn", i);
                magic(str, len-1, i);
                printf("----------------n");
        }
        return 0;
}

Ausgabe:

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

Als Antwort auf die Antwort von Kastrinis möchte ich überprüfen, ob dies auf mein Basisbeispiel wie folgt erweitert werden kann:

#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 %lun", i);
                magic(str, len-1, i);
                printf("----------------n");
        }
        return 0;
}

wobei die Ausgabe identisch ist.

_{PS – Ich schalte das Bit auch auf eine andere Weise um.}