アルゴリズムに少し行き詰まりました。問題を解決するために助けが必要です。例は私の問題をよりよく説明すると思います。
仮定:
- d = 4 (数値で許可される最大ビット数、2^4-1=15)。
- m_max = 1 (許容されるビット不一致の最大数)。
- kappa = (特定の d および m に対して検索する要素の最大数、ここで m は m_max 内)
主なアイデアは、与えられた数 x がその補数 (2 進数ベース) を計算し、x の補数から m_max までの不一致のすべての可能な組み合わせを計算することです。
プログラムは i = 0 から 15 までスキャンを開始します。
i = 0 および m = 0 の場合、kappa = \binom{d}{0} = 1 (これを完全一致と呼びます) の場合、可能なビットの組み合わせは 1111 (0: 0000 の場合) のみです。
i = 0 および m = 1 の場合、kappa = \binom{d}{1} = 4 (1 つの不一致) ビットの可能な組み合わせ: 1000、0100、0010、および 0001
私の問題は、それを一般的な d と m に一般化することでした。次のコードを書きました。
#include <stdlib.h>
#include <iomanip>
#include <boost/math/special_functions/binomial.hpp>
#include <iostream>
#include <stdint.h>
#include <vector>
namespace vec {
typedef std::vector<unsigned int> uint_1d_vec_t;
}
int main( int argc, char* argv[] ) {
int counter, d, m;
unsigned num_combination, bits_mask, bit_mask, max_num_mismatch;
uint_1d_vec_t kappa;
d = 4;
m = 2;
bits_mask = 2^num_bits - 1;
for ( unsigned i = 0 ; i < num_elemets ; i++ ) {
counter = 0;
for ( unsigned m = 0 ; m < max_num_mismatch ; m++ ) {
// maximum number of allowed combinations
num_combination = boost::math::binomial_coefficient<double>( static_cast<unsigned>( d ), static_cast<unsigned>(m) );
kappa.push_back( num_combination );
for ( unsigned j = 0 ; j < kappa.at(m) ; j++ ) {
if ( m == 0 )
v[i][counter++] = i^bits_mask; // M_0
else {
bit_mask = 1 << ( num_bits - j );
v[i][counter++] = v[i][0] ^ bits_mask
}
}
}
}
return 0;
}
v[i][counter++] = v[i][0] ^ bits_maskm_max の不一致 m_max ループに必要であり、元の問題では実行時まで m が不明であるため、アルゴリズムを m_max>1 に一般化できなかったため、行に行き詰まりました。