Suche nach n Bitvektoren mit Hamming-Distanz d zueinander.

goran

Hallo, ich suche numerisch eine handvoll (mehr ist numerisch nicht drin) Bitvektoren

std::bitset<N>

die alle zueinander die gleiche Hamming-Distanz aufweisen (ausser zu sich selbst).

In etwa sowas:

std::vector<std::bitset<256>> bitsets = do_magic<256>(3,100); // 3 Elemente, Distanz 100

if ( (bitsets[0]^bitsets[1]).count() == 100 &&
     (bitsets[0]^bitsets[2]).count() == 100 &&
     (bitsets[1]^bitsets[2]).count() == 100 )
  std::cout << "nice" << std::endl;

Wie sollte die Funktion

template <size_t N>
std::vector<std::bitset<N>> do_magic(size_t size, size_t dist);

definiert werden? Was meint ihr?

Danke

Bitte ein Bit

Eine schnelle Gedankenskizze
1.) Wähle Zahl A zufällig und trage diese in die Liste L ein
2.) Setze Zahl D (=Distanz) so dass die ersten X Bits gesetzt sind
3.) Berechne B = A xor D
4.) Füge B in L ein, sofern diese nicht schon vorhanden ist
5.) D = random_shuffle(D)

Die Idee dahinter ist folgende:
A xor B = A xor (A xor D) = 0 xor D = D

Denn wir rechne ich die Hamming Distanz aus? Ich berechne A xor B und zähle die Anzahl der gesetzten Bits. Und die ist in unserem Fall immer X.

Edit:
Kleinere Korrektur des letzten Satzes.

template <size_t N>
std::vector<std::bitset<N>> do_magic(size_t size, size_t dist)
{
	assert(N % 2 == 0);
	assert((N - dist / 2) / (dist / 2) >= size - 1);
	vector<bitset<N>> solution;
	solution.push_back(bitset<N>());

	for (int i = 1; i < size; ++i)
	{
		bitset<N> b;
		for (int j = 0; j < dist / 2; ++j)
		{
			b.set(j);
			b.set(i * dist / 2 + j);
		}
		solution.push_back(b);
	}
	return solution;
}

Das zweite assert kann man natürlich vereinfachen zu assert(2*N >= size * dist);

Und das erste assert sollte dist % 2 == 0 heißen. Die asserts sind sowieso etwas zu restriktiv bzw. der Algorithmus findet nicht immer eine Lösung, falls eine existiert. Bei N = 3, dist = 2 und size = 4 findet er z.B. nicht die Lösung {000,110,101,011}. Vielleicht reicht dir aber schon der gezeigte Algorithmus, denn er gibt zumindest immer korrekte Lösungen für den Fall dist % 2 == 0 && 2*n >= dist * size aus.

goran

Wau, sehr gut m.e. Ich verstehe noch nicht die for-Schleife aber das kommt gleich.

Vielen Dank