C++: compute a number's complement and its number of possible mismatches

Question

I got a bit stuck with my algorithm and I need some help to solve my problem. I think an example would explain better my problem.

Assuming:

• d = 4 (maximum number of allowed bits in a number, 2^4-1=15).
• m_max = 1 (maximum number of allowed bits mismatches).
• kappa = (maximum number of elements to find for a given d and m, where m in m_max)

The main idea is for a given number, x, to compute its complement number (in binary base) and all the possible combinations for up to m_max mismatches from x complement's number.

Now the program start to scan from i = 0 till 15.

• for i = 0 and m = 0, kappa = \binom{d}{0} = 1 (this called a perfect match) possible combinations in bits, is only 1111 (for 0: 0000).

• for i = 0 and m = 1, kappa = \binom{d}{1} = 4 (one mismatch) possible combinations in bits are: 1000, 0100, 0010 and 0001

My problem was to generalize it to general d and m. I wrote the following code:

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

}

I got stuck in the line v[i][counter++] = v[i][0] ^ bits_mask since I was unable to generalize my algorithm to m_max>1, since I needed for m_max mismatches m_max loops and in my original problem, m is unknown until runtime.

Answer 1

i wrote a code that do what i want, but since i am newbie, it is a bit ugly. i fixed m and d although this code would work fine for genral m and d.

the main idea is simple, assuming we would like to compute the complement of 0 up to two failure (d= 4,m=2), we will see that max number of possibilities is given by \sum_{i = 0)^2\binom{4}{i} = 11.
The complement to 0 (at 4 bits) is 15
With 1 bit possible mismatch (from 15): 7 11 13 14
with 2 bits possible mismatches (from 15): 3 5 6 9 10 12

i wanted that the output of this program will be a vector with the numbers 15 7 11 13 14 3 5 6 9 10 12 inside it.

i hope that this time i am more clear with presenting my question (although i also supplied the solution). I would appreachiate if someone could point out, in my code, ways to improve it and make it faster.

regards

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

    }
}