Генерация всех неупорядоченных пар строк битов с расстоянием Хэмминга не более 2
Я ищу эффективный способ для генерации всех неупорядоченных пар строк битов (представленных в виде целых чисел), которые имеют расстояние Хемминга не более 2. В этот ответ, показано, как это достаточно эффективно сделать для пар, имеющих расстояние Хэмминга 1.
Другими словами, ответ выше дает нам все края граф гиперкубов. В этих терминах я ищу эффективный способ создания краев площадь гиперкуба.
Есть ли хороший известный быстрый метод, возможно, аналогично основанный на битовых уловках?
Решение
Есть легкая модификация Нейт Коля ответ.
int n = 3;
// examine all vertices from 0...2^n-1
unsigned long long max = 1ULL << n;
for (unsigned long long vertex = 0; vertex < max; ++vertex) {
std::cout << vertex << ':';
// print all vertices that differ from vertex by one bit
unsigned long long mask = 1;
for (int shift_amt = 0; shift_amt < n; ++shift_amt) {
std::cout << ' ' << (vertex ^ (mask << shift_amt));
}
for (int shift_amt1 = 0; shift_amt1 < n; ++shift_amt1) {
for (int shift_amt2 = 0; shift_amt2 < shift_amt1; ++shift_amt2) {
std::cout << ' ' << (vertex ^ (mask << shift_amt1) ^ (mask << shift_amt2));
}
}
std::cout << '\n';
}
Другие решения
Других решений пока нет …