Algorithme permettant de retourner toutes les combinaisons de k éléments parmi n

Question

Je veux écrire une fonction qui prend un tableau de lettres comme argument et un nombre de ces lettres à sélectionner.

Disons que vous fournissez un tableau de 8 lettres et que vous voulez en sélectionner 3. Alors vous devriez obtenir :

8! / ((8 - 3)! * 3!) = 56

Des tableaux (ou mots) en retour composés de 3 lettres chacun.

Answer 1

L'algorithme récursif suivant sélectionne toutes les combinaisons de k éléments dans un ensemble ordonné :

• choisir le premier élément i de votre combinaison
• moissonneuse-batteuse i avec chacune des combinaisons de k-1 éléments choisis récursivement dans l'ensemble des éléments plus grands que i .

Itérer ce qui précède pour chaque i dans le jeu.

Il est essentiel que vous choisissiez le reste des éléments comme plus grands que i afin d'éviter les répétitions. De cette façon, [3,5] sera choisi une seule fois, en tant que [3] combiné à [5], au lieu de deux fois (la condition élimine [5] + [3]). Sans cette condition, on obtient des variations au lieu de combinaisons.

Answer 2

Petit exemple en Python :

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

À titre d'explication, la méthode récursive est décrite à l'aide de l'exemple suivant :

Exemple : A B C D E
Toutes les combinaisons de 3 le seraient :

• A avec toutes les combinaisons de 2 du reste (B C D E)
• B avec toutes les combinaisons de 2 du reste (C D E)
• C avec toutes les combinaisons de 2 du reste (D E)

Answer 3

En C++, la routine suivante produira toutes les combinaisons de longueur distance(first,k) entre l'intervalle [first,last] :

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Il peut être utilisé comme suit :

#include <string>
#include <iostream>

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

    return 0;
}

L'impression sera la suivante :

123
124
125
134
135
145
234
235
245
345

Answer 4

J'ai trouvé ce fil de discussion utile et j'ai pensé ajouter une solution Javascript que vous pouvez insérer dans Firebug. En fonction de votre moteur JS, cela peut prendre un peu de temps si la chaîne de départ est grande.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

Le résultat devrait être le suivant :

abc
ab
ac
a
bc
b
c

Answer 5

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}