0

我的算法有点卡住了，我需要一些帮助来解决我的问题。我认为一个例子可以更好地解释我的问题。

假设：

  • d = 4（一个数字中允许的最大位数，2^4-1=15）。
  • m_max = 1（允许的最大位数不匹配）。
  • kappa =（对于给定的 d 和 m，要查找的最大元素数，其中 m 在 m_max 中）

主要思想是对于给定的数字 x，计算其补数（以二进制为基数）以及与 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（一个不匹配）可能的位组合是：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_mask因为我无法将我的算法推广到 m_max>1，因为我需要 m_max 不匹配 m_max 循环，并且在我的原始问题中，m 在运行时之前是未知的。

4

1 回答 1

0

我写了一个做我想做的代码，但因为我是新手，所以有点难看。我修复了 m 和 d，尽管此代码适用于一般 m 和 d。

主要思想很简单，假设我们要计算 0 到最多两次失败 (d= 4,m=2) 的补码，我们将看到最大可能性数由 给出\sum_{i = 0)^2\binom{4}{i} = 11。
0 的补码（4 位）是 15
1 位可能不匹配（来自 15）：7 11 13 14
有 2 位可能不匹配（来自 15）：3 5 6 9 10 12

我希望这个程序的输出是一个向量，里面有数字 15 7 11 13 14 3 5 6 9 10 12。

我希望这次我能更清楚地提出我的问题（尽管我也提供了解决方案）。如果有人可以在我的代码中指出改进它并使其更快的方法，我会很高兴。

问候

#include <boost/math/special_functions/binomial.hpp>
#include <iostream>
#include <vector>

#define USE_VECTOR

namespace vec {
  #if defined(USE_VECTOR) || !defined(USE_DEQUE)
  typedef std::vector<unsigned int>  uint_1d_vec_t;
  typedef std::vector<uint_1d_vec_t> uint_2d_vec_t;
  #else
  typedef std::deque<unsigned int>   uint_1d_vec_t;
  typedef std::deque<uint_1d_vec_t>  uint_2d_vec_t;
  #endif
}

using namespace std;

void     get_pointers_vec( vec::uint_2d_vec_t &v , unsigned num_elemets , unsigned      max_num_unmatch , unsigned num_bits );
double   get_kappa( int m , int d );

int main( ) { 

    unsigned int num_elements , m , num_bits;

    num_elements = 16; 
    num_bits     = 4;   // 2^4 = 16
    m            = 2;

    double kappa = 0;
    for ( unsigned int i = 0 ; i <= m ; i++ )
        kappa += get_kappa( num_bits , i );

    vec::uint_2d_vec_t    Pointer(           num_elements   , vec::uint_1d_vec_t (kappa ,0 ) );

    get_pointers_vec( Pointer , num_elements , m , num_bits );

    for ( unsigned int i = 0 ; i < num_elements ; i++ ) {
        std::cout << setw(2) << i << ":";
        for ( unsigned int j = 0 ; j < kappa ; j++ )
            std::cout << setw(3) << Pointer[i][j];
        std::cout << std::endl;
    }

    return EXIT_SUCCESS;
}

double get_kappa( int n , int k ) {

    double kappa = boost::math::binomial_coefficient<double>( static_cast<unsigned>( n ), static_cast<unsigned>(k) );

    return kappa;
}

void get_pointers_vec( vec::uint_2d_vec_t &v , unsigned num_elemets , unsigned   max_num_unmatch , unsigned num_bits ) {

    int counter;
    unsigned num_combination, ref_index, bits_mask, bit_mask;
    vec::uint_1d_vec_t kappa;

    bits_mask = pow( 2 , num_bits ) - 1;
    for ( unsigned i = 0 ; i < num_elemets ; i++ ) {
        counter = 0;
        kappa.clear();
        ref_index = 0;

        for ( unsigned m = 0 ; m <= max_num_unmatch ; m++ ) {
            num_combination = get_kappa( num_bits , m ); // maximum number of allowed combinations
            kappa.push_back( num_combination );
            if (  m == 0 ) {
               v[i][counter++] = i^bits_mask; // M_0
            }
            else if ( num_bits == kappa.at(m) ) {

                     for ( unsigned k = m ; k <= num_bits ; k++ ) {
                         bit_mask = 1 << ( num_bits - k );
                         v[i][counter++] = v[i][ref_index] ^ bit_mask;
                     }
                }
                else {
                     // Find first element's index
                     ref_index += kappa.at( m - 2 );

                     for( unsigned j = 0 ; j < ( kappa.at(m - 1) - 1 ) ; j++ ) {
                         for ( unsigned k = m + j ; k <= num_bits ; k++ ) {
                             bit_mask = 1 << ( num_bits - k );
                             v[i][counter++] = v[i][ref_index] ^ bit_mask;
                         }
                         ref_index++;
                     }
                }
        }

    }
}
于 2009-12-13T22:20:44.993 回答