toutes les combinaisons de K éléments sur n

Quelqu'un peut-il me fournir un lien ou un pseudocode d'une fonction pour trouver toutes les combinaisons de K éléments sur n? éventuellement dans la STL. Je n'ai pas besoin de calculer n choisir k, j'ai besoin de lister tous les vecteurs de nombres de taille K.

Merci

22
demandé sur Tamas 2011-02-23 21:34:05

5 réponses

En C++ étant donné 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 comme suit: 

// 9-choose-3 
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()));

Ou pour un STD:: vecteur de int: 

// 5-choose-3 
std::size_t n = 5;
std::size_t k = 3;

std::vector<int> ints;
for (int i = 0; i < n; ints.push_back(i++));

do
{
   for (int i = 0; i < k; ++i)
   {
      std::cout << ints[i];
   }
   std::cout << "\n";
}
while(next_combination(ints.begin(),ints.begin() + k,ints.end()));
24
répondu 2011-02-23 21:11:12

Http://howardhinnant.github.io/combinations.html

Recherche "for_each_combination". Si vous trouvez quelque chose de plus rapide, faites-le moi savoir. Contrairement à d'autres algorithmes que je vois souvent, celui-ci ne nécessite pas que le type d'élément soit LessThanComparable.

9
répondu Howard Hinnant 2014-09-21 20:09:37

Crée un vecteur auxiliaire avec n-k zéros suivis de K uns. Un zéro signifie que l'élément dans le conteneur d'origine n'est pas inclus, alors que l'on signifie que l'élément est inclus.

Maintenant, utilisez std:: next_permutation sur le vecteur auxiliaire pour obtenir la combinaison suivante.

3
répondu user515430 2011-02-23 22:37:26

Voici un exemple paresseux de pseudocode qui peut faire le travail...

void nChooseK(array[n],k){
    recurse("",array[n],k);      
}

void recurse(initialString,array[n],k){
    if(k == 0){
        print initialString;
        return;
     }
    for(i=0;i<n;i++){
        tmpArray = array[0...i-1]+array[i+1...];//the array without the object to remove
        recurse(initialString + array[i], tmpArray,k-1)
    }        
}
1
répondu nosirrahcd 2011-02-23 20:02:34

Vous pouvez utiliser std::next_permutation, mais il est n! et non n choisissez K. Vous pouvez les filtrer après les avoir créés. Mais cette solution est O (n!), pas vraiment parfait. Voici la solution d'essai et d'erreur: 

int factorial(int value)
{
    int result = 1;

    for(int i = 1; i <= value; i++)
    {
        result *= i;
    }

    return result;
}

std::set<std::set<int>> binomial_coefficient(std::vector<int> input, int k)
{
    std::set<std::set<int>> solutions;

    for(unsigned int i = 0; i < factorial(input.size()); i++)
    {
        std::next_permutation(input.begin(), input.end());

        solutions.insert(std::set<int>(input.begin(), input.begin() + k));
    }

    return solutions;
}
0
répondu Fox32 2011-02-23 19:44:26