Nombre de combinaisons (N choisir R) dans C++

Votre formule est totalement faux, c'est censé être fact(n)/fact(r)/fact(n-r), mais qui est à son tour une voie très inefficace pour le calculer.

Voir Un calcul rapide de multi-catégorie nombre de combinaisons et surtout mes commentaires sur cette question. (Oh, et merci de revenir sur cette question afin que je puisse répondre correctement)

Le single split cas est en fait très facile à manipuler:

unsigned nChoosek( unsigned n, unsigned k )
{
    if (k > n) return 0;
    if (k * 2 > n) k = n-k;
    if (k == 0) return 1;

    int result = n;
    for( int i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}

Démo: http://ideone.com/aDJXNO

Si le résultat ne convient pas, vous pouvez calculer la somme des logarithmes et obtenir le nombre de combinaisons inexactly comme un double. Ou l'utilisation d'une précision arbitraire entier de la bibliothèque.

---

Je suis en train de mettre ma solution à l'autre, étroitement liés à la question ici, parce que ideone.com a été de perdre des extraits de code dernièrement, et l'autre question est toujours fermé à de nouvelles réponses.

#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i )
factor_table[i] = std::pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
}
}
std::vector<unsigned> powers;
template<int dir>
void factor( int num )
{
while (num != 1) {
powers[factor_table[num].first] += dir;
num = factor_table[num].second;
}
}
template<unsigned N>
void calc_combinations(unsigned (&bin_sizes)[N])
{
using std::swap;
powers.resize(0);
if (N < 2) return;
unsigned& largest = bin_sizes[0];
size_t sum = largest;
for( int bin = 1; bin < N; ++bin ) {
unsigned& this_bin = bin_sizes[bin];
sum += this_bin;
if (this_bin > largest) swap(this_bin, largest);
}
fill_sieve(sum);
powers.resize(sum+1);
for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
for( unsigned bin = 1; bin < N; ++bin )
for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
}
#include <iostream>
#include <cmath>
int main(void)
{
unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };
calc_combinations(bin_sizes);
char* sep = "";
for( unsigned i = 0; i < powers.size(); ++i ) {
if (powers[i]) {
std::cout << sep << i;
sep = " * ";
if (powers[i] > 1)
std::cout << "**" << powers[i];
}
}
std::cout << "\n\n";
}

OriginalL'auteur Ben Voigt

Une belle façon de mettre en œuvre des n-choisissez-k est à la base pas sur les factorielles, mais sur une "la hausse des produits de la fonction" qui est étroitement liée à la factorielle.

La rising_product(m, n) multiplie ensemble m * (m + 1) * (m + 2) * ... * n, avec des règles pour la gestion des divers cas de coin, comme n >= m, ou n <= 1:

Voir ici pour une mise en œuvre nCk ainsi que les nPk en tant que fonctions intrinsèques dans un langage de programmation interprété écrit en C:

static val rising_product(val m, val n)
{
val acc;
if (lt(n, one))
return one;
if (ge(m, n))
return one;
if (lt(m, one))
m = one;
acc = m;
m = plus(m, one);
while (le(m, n)) {
acc = mul(acc, m);
m = plus(m, one);
}
return acc;
}
val n_choose_k(val n, val k)
{
val top = rising_product(plus(minus(n, k), one), n);
val bottom = rising_product(one, k);
return trunc(top, bottom);
}
val n_perm_k(val n, val k)
{
return rising_product(plus(minus(n, k), one), n);
}

Ce code ne nécessite pas d'utiliser des opérateurs comme + et < car il est de type générique (le type val représente une valeur de toutes les sortes, tels que divers types de nombres, y compris "bignum" entiers) et parce que c'est écrit en C (pas de surcharge), et parce que c'est la base pour un Lisp comme les langues qui n'ont pas infix syntaxe.

En dépit de cela, ce n-choisissez-k de la mise en œuvre a une structure simple qui est facile à suivre.

Légende: le: inférieur ou égal; ge: supérieure ou égale; trunc: la troncation de la division; plus: plus, mul: multiplication, one: un val tapé constante pour le numéro un.

OriginalL'auteur Kaz

Utilisation double au lieu de int.

Mise à JOUR:

Votre formule est également faux. Vous devez utiliser fact(n)/fact(r)/fact(n-r)

OriginalL'auteur Pulkit Goyal