Calculer la combinaison en fonction de la position

Il semble que vous souhaitiez trouver la combinaison k pour un nombre donné .

En suivant l’ exemple , voici quelque chose qui devrait fonctionner:

#include  #include  #include  #include  #include  std::size_t Choose(double n, double k) { using boost::math::binomial_coefficient; if (n < k) return 0; return static_cast(binomial_coefficient(n, k)); } // Returns the largest n such that Choose(n, k) <= pos. int CombinationElement(int k, int pos) { int n = k; int coeff = 1, prev_coeff = 0; while (coeff <= pos) { coeff = Choose(++n, k); prev_coeff = coeff; } return n - 1; } // Returns an k-combination at position pos. std::vector Combination(int k, int pos) { std::vector combination; for (; k > 0; --k) { int n = CombinationElement(k, pos); combination.push_back(n); pos -= Choose(n, k); } return combination; } int main(int argc, char** argv) { using std::cout; using std::endl; if (argc != 3) { cout << "Usage: $ " << argv[0] << " K POS" << endl; cout << "Prints the K-combination at position POS." << endl; return 1; } int k = boost::lexical_cast(argv[1]); int pos = boost::lexical_cast(argv[2]); std::vector combination = Combination(k, pos); for (int i = 0; i < k; i++) cout << combination[i] << " "; cout << std::endl; } 

Notez que par commodité, le code dépend de Boost pour calculer les coefficients binomiaux ( boost::math::binomial_coefficient ) et pour parsingr les chaînes en entiers ( boost::lexical_cast ).

Voici une implémentation dans Mathematica du paquet Combinatorica . La sémantique est assez générique, donc je pense que c’est utile. S’il vous plaît laissez un commentaire si vous avez besoin de quoi que ce soit expliqué.

 UnrankKSubset::usage = "UnrankKSubset[m, k, l] gives the mth k-subset of set l, listed in lexicographic order." UnrankKSubset[m_Integer, 1, s_List] := {s[[m + 1]]} UnrankKSubset[0, k_Integer, s_List] := Take[s, k] UnrankKSubset[m_Integer, k_Integer, s_List] := Block[{i = 1, n = Length[s], x1, u, $RecursionLimit = Infinity}, u = Binomial[n, k]; While[Binomial[i, k] < u - m, i++]; x1 = n - (i - 1); Prepend[UnrankKSubset[m - u + Binomial[i, k], k-1, Drop[s, x1]], s[[x1]]] ] 

L'utilisation est comme:

 UnrankKSubset[1, 4, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}] 

  {1, 2, 3, 5} 

Comme vous pouvez le constater, cette fonction s’applique aux ensembles.

Ci-dessous ma tentative d'expliquer le code ci-dessus.

UnrankKSubset est une fonction récursive à trois arguments, appelée (m, k, s):

1. m un entier, le "rang" de la combinaison dans l'ordre lexigraphique, en partant de zéro.
2. k un entier, le nombre d'éléments dans chaque combinaison
3. s une liste, les éléments à partir desquels assembler des combinaisons

Il y a deux conditions aux limites sur la récursivité:

1. pour tout rang m , et toute liste s , si le nombre d'éléments dans chaque combinaison k est 1 , alors:

   renvoie l'élément m + 1 de la liste s , elle-même dans une liste.

   ( + 1 est nécessaire parce que Mathematica indexe un, plutôt que zéro. Je crois qu'en C ++, ce serait s [m])

2. si le rang m est 0 alors pour tout k et tout s :

   renvoyer les k premiers éléments de s

La fonction récursive principale, pour tous les arguments autres que ceux spécifiés ci-dessus:

variables locales: ( i , n , x1 , u )

Binomial est le coefficient Binomial[7, 5] : Binomial[7, 5] = 21

Faire:

 i = 1 n = Length[s] u = Binomial[n, k] While[Binomial[i, k] < u - m, i++]; x1 = n - (i - 1); 

Puis retournez:

 Prepend[ UnrankKSubset[m - u + Binomial[i, k], k - 1, Drop[s, x1]], s[[x1]] ] 

C'est-à-dire, "ajoutez" l'élément x1 de la liste s (rappelez-vous des index Mathematica, alors je pense que ce serait l'index x1 - 1 en C ++) de la liste renvoyée par la fonction UnrankKSubset appelée récursivement avec les arguments:

• m - u + Binomial[i, k]
• k - 1
• Drop[s, x1]

Drop[s, x1] est le rest de la liste s avec les premiers éléments x1 supprimés.

Si ce qui précède n’est pas compréhensible, ou si vous vouliez une explication de l’algorithme plutôt que du code, laissez un commentaire et laissez-moi réessayer.