Liste toutes les combinaisons possibles de k entiers entre 1 ... n (n choisir k)

Question

Sans raison particulière, j'ai décidé de rechercher un algorithme qui produit tous les choix possibles de k entiers entre 1 ... n, où le l'ordre parmi les k entiers n'a pas d'importance (les n choisissent k thingy). De la même raison, ce qui n'est pas une raison du tout, je l'ai également implémenté en C#. Ma question est:

Voyez-vous une erreur dans mon algorithme ou mon code? Et, plus important, pouvez-vous suggérer un meilleur algorithme?

Veuillez accorder plus d'attention à l'algorithme que le code lui-même. Ce n'est pas le plus joli code que j'ai jamais écrit, mais dites-le si vous voyez une erreur.

EDIT: Alogirthm expliqué -

• Nous détenons des indices k.
• Ceci crée imbriqué pour les boucles, où l'index de la boucle i est index [i].
• Il simule k pour boucles où les indices [i + 1] appartiennent à une boucle imbriquée dans la boucle d'indices [i].
• indices [i] des indices [Runs i - 1] + 1 à n - k + i + 1.

CODE:

public class AllPossibleCombination 
{ 
    int n, k; 
    int[] indices; 
    List<int[]> combinations = null; 

    public AllPossibleCombination(int n_, int k_) 
    { 
     if (n_ <= 0) 
     { 
      throw new ArgumentException("n_ must be in N+"); 
     } 
     if (k_ <= 0) 
     { 
      throw new ArgumentException("k_ must be in N+"); 
     } 
     if (k_ > n_) 
     { 
      throw new ArgumentException("k_ can be at most n_"); 
     } 

     n = n_; 
     k = k_; 
     indices = new int[k]; 
     indices[0] = 1; 
    } 

    /// <summary> 
    /// Returns all possible k combination of 0..n-1 
    /// </summary> 
    /// <returns></returns> 
    public List<int[]> GetCombinations() 
    { 
     if (combinations == null) 
     { 
      combinations = new List<int[]>(); 
      Iterate(0); 
     } 
     return combinations; 
    } 

    private void Iterate(int ii) 
    { 
     // 
     // Initialize 
     // 
     if (ii > 0) 
     { 
      indices[ii] = indices[ii - 1] + 1; 
     } 

     for (; indices[ii] <= (n - k + ii + 1); indices[ii]++) 
     { 
      if (ii < k - 1) 
      { 
       Iterate(ii + 1); 
      } 
      else 
      { 
       int[] combination = new int[k]; 
       indices.CopyTo(combination, 0); 
       combinations.Add(combination); 
      } 
     } 
    } 
} 

Je présente mes excuses pour la longue question, il pourrait être en forme pour un blog, mais je veux l'opinion de la communauté ici.

Merci,
Asaf

Answer 1

Voici un programme relativement simple, nCr/efficace je l'ai écrit il y a un moment dans C:

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);} 

D'accord ... version lisible. =] (Je ne sais pas si cela est de 1: 1. Correspondant au-dessus)

void nCr(int n, int k) { 
    float curK = 0, r = 1; 
    while(curK < k) { 
     ++curK; 
     printf("%.0f\n", r); 
     r *= (1 + n - curK)/curK; 
    } 
} 

au lieu d'imprimer, vous pourriez yield ou quoi (je ne sais pas C#) dans votre liste.

Answer 2

Asaf,

Vous nous demandez d'évaluer votre algorithme, mais vous n'explique pas votre algorithme - même pas dans les commentaires de code. Donc, vous voulez que tout le monde passe une heure ou plus à l'ingénierie inverse de l'algorithme du code, juste pour que nous puissions comprendre votre question avant de répondre?

Veuillez éditer votre question pour expliquer votre algorithme. Une chose est évidente: l'empreinte mémoire de votre code est épouvantable. Pour des valeurs modestes de n, le nombre de combinaisons sera facilement de plusieurs milliards, ce qui nécessitera plus de mémoire que la plupart des ordinateurs. De plus, vous utilisez des tableaux développés dynamiquement, qui continuent de se réaffecter et de se copier à mesure qu'ils grandissent.De plus, votre programme génère des sous-ensembles dans différents tableaux et les fusionne. Dans l'ensemble, votre programme nécessitera plusieurs fois la quantité de mémoire qui serait idéalement nécessaire pour stocker la liste, et il passera le plus clair de son temps à simplement copier les données d'avant en arrière.

Si doit avoir toutes les valeurs dans un tableau à la fois, commencez au moins en calculant la taille du tableau dont vous avez besoin - n!/(n-k)!/k! - et ensuite juste le remplir.

Encore mieux serait le code que "paresseusement" juste calculé chaque membre de la séquence comme il le fallait. Voir this question from the related questions sidebar

Answer 3

En C++ compte tenu de la routine suivante:

template <typename Iterator> 
inline bool next_combination(const Iterator first, Iterator k, const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

Vous pouvez ensuite procéder à effectuer les opérations suivantes:

std::string s = "123456789"; 
std::size_t k = 3; 
do 
{ 
    std::cout << std::string(s.begin(),s.begin() + k) << std::endl; 
} 
while(next_combination(s.begin(),s.begin() + k,s.end())); 

Answer 4

Ce gars semble avoir fait un travail sérieux dans combinatoires en utilisant C# (CodeProject):

Permutations, Combinations, and Variations using C# Generics