C++: calculer le complément d'un nombre et son nombre de discordances possibles

Question

Je me suis un peu coincé avec mon algorithme et j'ai besoin d'aide pour résoudre mon problème. Je pense qu'un exemple expliquerait mieux mon problème.

En supposant que:

• d = 4 (nombre maximal de bits autorisés dans un certain nombre, 2^4-1 = 15).
• m_max = 1 (nombre maximal de mésappariements de bits autorisés).
• kappa = (nombre maximal d'éléments à trouver pour une donnée d et m, où m dans m_max)

L'idée principale est pour un nombre donné, x, pour calculer le numéro de complément (en base binaire) et toutes les combinaisons possibles jusqu'à m_max mismatches de x nombre de complément.

Maintenant, le programme pour numériser de i = 0 à 15.

• pour i = 0 et m = 0, kappa = \ binom {d} {0} = 1 (appelé un parfait match) combinaisons possibles en bits, est seulement 1111 (pour 0: 0000).

• pour i = 0 et m = 1, kappa = \ binom {d} {1} = 4 (une non-concordance) combinaisons possibles de bits sont: 1000, 0100, 0010 et 0001

Mon problème était de généraliser à général d et m. J'ai écrit le code suivant:

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

} 

Je suis coincé dans la ligne v[i][counter++] = v[i][0]^bits_mask depuis que je suis incapable de généraliser mon algorithme à m_max> 1, depuis que je avais besoin pour inadéquations m_max m_max boucles et dans mon problème d'origine, m est inconnu jusqu'à l'exécution.

Answer 1

J'ai écrit un code qui fait ce que je veux, mais depuis que je suis novice, c'est un peu moche. j'ai fixé m et d bien que ce code fonctionnerait bien pour genral m et d.

l'idée principale est simple, en supposant que nous aimerions calculer le complément de 0 jusqu'à deux échec (d = 4, m = 2), nous verrons que le nombre maximum de possibilités est donné par \sum_{i = 0)^2\binom{4}{i} = 11.
Le complément à 0 (à 4 bits) est 15
avec 1 bit non-concordance possible (de 15): 7 11 13 14
avec 2 bits mésappariements possibles (de 15): 3 5 6 9 10 12

Je voulais que la sortie de ce programme soit un vecteur avec les numéros 15 7 11 13 14 3 5 6 9 10 12 à l'intérieur.

J'espère que cette fois je suis plus clair avec présenter ma question (bien que j'ai également fourni la solution). J'apprécierais si quelqu'un pouvait indiquer, dans mon code, des façons de l'améliorer et de le rendre plus rapide.

concernant

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

    } 
}