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

Algorithme récursif simple en Haskell

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

Nous définissons d'abord le cas particulier, c'est-à-dire la sélection de zéro élément. Il produit un seul résultat, qui est une liste vide (c'est-à-dire une liste qui contient une liste vide).

Pour n > 0, x parcourt chaque élément de la liste et xs est chaque élément après x .

rest picks n - 1 des éléments de xs en utilisant un appel récursif à combinations . Le résultat final de la fonction est une liste dont chaque élément est x : rest (c'est-à-dire une liste qui a x comme chef et rest comme queue) pour chaque valeur différente de x y rest .

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Et bien sûr, comme Haskell est paresseux, la liste est générée progressivement selon les besoins, de sorte que vous pouvez évaluer partiellement des combinaisons de taille exponentielle.

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

Answer 2

Et voici le grand-père COBOL, le langage tant décrié.

Supposons un tableau de 34 éléments de 8 octets chacun (sélection purement arbitraire.) L'idée est d'énumérer toutes les combinaisons possibles de 4 éléments et de les charger dans un tableau.

Nous utilisons 4 indices, un pour chaque position dans le groupe de 4

Le tableau est traité comme suit :

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

Nous faisons varier idx4 de 4 à la fin. Pour chaque idx4 nous obtenons une combinaison unique de groupes de quatre. Lorsque idx4 arrive à la fin du tableau, nous incrémentons idx3 de 1 et fixons idx4 à idx3+1. Puis nous faisons à nouveau passer idx4 jusqu'à la fin. Nous procédons de cette manière, en augmentant idx3, idx2 et idx1 respectivement jusqu'à ce que la position de idx1 soit à moins de 4 de la fin du tableau. Cela termine l'algorithme.

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

Premières itérations :

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

Un exemple en COBOL :

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

---

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

Answer 3

Si vous pouvez utiliser la syntaxe SQL - par exemple, si vous utilisez LINQ pour accéder aux champs d'une structure ou d'un tableau, ou si vous accédez directement à une base de données qui possède une table appelée "Alphabet" avec un seul champ de caractères "Lettre", vous pouvez adapter le code suivant :

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

Cela donnera toutes les combinaisons de 3 lettres, quel que soit le nombre de lettres du tableau "Alphabet" (3, 8, 10, 27, etc.).

Si ce que vous voulez, ce sont toutes les permutations, plutôt que les combinaisons (c'est-à-dire que vous voulez que "ACB" et "ABC" comptent comme différents, plutôt que d'apparaître une seule fois), supprimez simplement la dernière ligne (la ligne AND) et c'est fait.

Post-Edit : Après avoir relu la question, je réalise que ce qui est nécessaire est le général et pas seulement un algorithme spécifique pour le cas de la sélection de 3 éléments. La réponse d'Adam Hughes est la réponse complète, malheureusement je ne peux pas la voter (encore). Cette réponse est simple mais ne fonctionne que lorsque l'on veut exactement 3 éléments.

Answer 4

Une autre version C# avec la génération paresseuse des indices de combinaison. Cette version maintient un seul tableau d'indices pour définir un mappage entre la liste de toutes les valeurs et les valeurs de la combinaison actuelle, c'est-à-dire qu'elle utilise en permanence O(k) espace supplémentaire pendant toute la durée de l'exécution. Le code génère les combinaisons individuelles, y compris la première, en O(k) temps.

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

Code de test :

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

Output:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

Answer 5

Voici une implémentation élégante et générique en Scala, telle que décrite sur 99 problèmes de Scala .

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}