Algorithme pour renvoyer toutes les combinaisons de k éléments de n

https://stackoverflow.com/questions/127704

02-07-2019
|

Question

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

Supposons que vous fournissiez un tableau de 8 lettres et que vous souhaitiez en sélectionner 3. Ensuite, vous devriez obtenir:

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

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

La solution

L'art de la programmation informatique volume 4: Le fascicule 3 en contient une tonne qui conviendrait mieux à votre situation particulière que celle que je décris.

Codes gris

Un problème que vous rencontrerez est bien sûr la mémoire et assez rapidement, vous aurez des problèmes de 20 éléments dans votre ensemble - ²⁰ C ₃ = 1140 Et si vous souhaitez parcourir l'ensemble, il est préférable d'utiliser un algorithme de code gris modifié afin de ne pas les conserver tous en mémoire. Ceux-ci génèrent la combinaison suivante à partir de la précédente et évitent les répétitions. Il y en a beaucoup pour des utilisations différentes. Voulons-nous maximiser les différences entre les combinaisons successives? minimiser? et cetera.

Certains des documents originaux décrivant les codes gris:

Voici d'autres articles sur le sujet:

Une mise en œuvre efficace de Eades, Hickey, Lire l'échange adjacent Algorithme de génération de combinaison (PDF, avec code en Pascal)
générateurs combinés
Enquête sur les codes gris combinatoires (PostScript)
Un algorithme pour les codes gris

Twiddle de Chase (algorithme)

Phillip J Chase, ` Algorithme 382: Combinaisons de M sur N objets '(1970)

L'algorithme en C ...

Index des combinaisons en ordre lexicographique (algorithme de boucles 515)

Vous pouvez également référencer une combinaison par son index (par ordre lexicographique). En réalisant que l’indice doit être modifié de droite à gauche en fonction de l’index, nous pouvons construire quelque chose qui devrait récupérer une combinaison.

Donc, nous avons un ensemble {1,2,3,4,5,6} ... et nous voulons trois éléments. Disons que {1,2,3} on peut dire que la différence entre les éléments est un et dans l’ordre et minimale. {1,2,4} a un changement et est lexicographiquement numéro 2. Ainsi, le nombre de "changements" à la dernière place compte pour un changement dans l'ordre lexicographique. La deuxième place, avec un changement, {1,3,4}, a un changement, mais représente plus de changements depuis sa deuxième place (proportionnelle au nombre d’éléments de l’ensemble initial).

La méthode que j'ai décrite est une déconstruction, semble-t-il, de jeu en index, nous devons faire l'inverse & # 8211; ce qui est beaucoup plus compliqué. C’est ainsi que Boucles résout le problème. J'ai écrit des C pour les calculer , avec des modifications mineures < !> # 8211; J'ai utilisé l'indice des ensembles plutôt qu'une plage de nombres pour représenter l'ensemble, nous travaillons donc toujours de 0 à n. Remarque:

Les combinaisons étant non ordonnées, {1,3,2} = {1,2,3} - nous les ordonnons d'être lexicographiques.
Cette méthode a un 0 implicite pour démarrer l'ensemble pour la première différence.

Index des combinaisons dans le LexicograpOrdre hical (McCaffrey)

Il y a d’une autre manière :, son concept est plus facile à comprendre et à programmer mais sans les optimisations de Buckles. Heureusement, cela ne produit pas non plus de combinaisons dupliquées:

L'ensemble qui maximise , où .

Pour un exemple: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). La 27ème combinaison lexicographique de quatre choses est donc: {1,2,5,6}, ce sont les index de l’ensemble que vous voulez regarder. Exemple ci-dessous (OCaml), requiert la choose fonction laissée au lecteur:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

Un petit et simple itérateur de combinaisons

Les deux algorithmes suivants sont fournis à des fins didactiques. Ils implémentent un itérateur et des combinaisons globales de dossiers (plus générales). Ils sont aussi rapides que possible, avec la complexité O (ⁿ C _k). La consommation de mémoire est liée à k.

Nous allons commencer par l'itérateur, qui appellera une fonction fournie par l'utilisateur pour chaque combinaison

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

Une version plus générale appellera la fonction fournie par l'utilisateur avec la variable d'état, à partir de l'état initial. Puisque nous devons passer d'un état à un autre, nous n'utiliserons pas la boucle for, nous utiliserons plutôt la récursivité,

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

Autres conseils

En C #:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

Utilisation:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Résultat:

Solution Java courte:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

Le résultat sera

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

Puis-je présenter ma solution récursive en Python à ce problème?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Exemple d'utilisation:

>>> len(list(choose_iter("abcdefgh",3)))
56

Je l’aime pour sa simplicité.

Disons que votre tableau de lettres ressemble à ceci: & "; ABCDEFGH &"; Vous avez trois index (i, j, k) indiquant les lettres que vous allez utiliser pour le mot actuel. Vous commencez par:

A B C D E F G H
^ ^ ^
i j k

D'abord, vous faites varier k, la prochaine étape est la suivante:

A B C D E F G H
^ ^   ^
i j   k

Si vous avez atteint la fin, vous continuez et vous modifiez j puis k à nouveau.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Une fois que vous avez atteint J, vous commencez également à varier.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

Écrit dans le code suivant, cela ressemble à quelque chose comme ça

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

L’algorithme récursif suivant sélectionne toutes les combinaisons d’éléments k à partir d’un ensemble ordonné:

choisissez le premier élément i de votre combinaison
combinez k-1 avec chacune des combinaisons de <=> éléments choisis récursivement dans l'ensemble d'éléments supérieurs à <=>.

Itérer ce qui précède pour chaque <=> ensemble.

Il est essentiel que le reste des éléments soit supérieur à <=> pour éviter les répétitions. De cette façon, [3,5] ne sera sélectionné qu'une fois, comme [3] combiné avec [5], au lieu de deux (la condition élimine [5] + [3]). Sans cette condition, vous obtenez des variations au lieu de combinaisons.

J'ai trouvé ce fil 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

En C ++, la routine suivante produira toutes les combinaisons de longueur distance (premier, k) entre la plage [premier, dernier):

#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 ceci:

#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;
}

Ceci imprimera ce qui suit:

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;
    }
}

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

Pour plus d'explications, 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 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)

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 en sélectionnant zéro élément. Il produit un seul résultat, qui est une liste vide (c'est-à-dire une liste contenant une liste vide).

Pour n > 0, x passe en revue tous les éléments de la liste et xs correspond à tous les éléments après rest.

n - 1 choisit combinations des éléments de x : rest en utilisant un appel récursif à <=>. Le résultat final de la fonction est une liste où chaque élément est <=> (c'est-à-dire une liste ayant <=> en tête et <=> en queue) pour chaque valeur différente de <=> et <=>.

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

Et bien sûr, Haskell étant paresseux, la liste est générée au fur et à mesure, de sorte que vous puissiez évaluer partiellement des combinaisons exponentiellement grandes.

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

Et voici papy 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 définissons idx4 sur idx3 + 1. Ensuite, nous courons encore idx4 à la fin. Nous procédons de cette manière, en augmentant idx3, idx2 et idx1 respectivement jusqu'à ce que la position de idx1 soit inférieure à 4 à partir 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:

Un exemple 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.

Voici une mise en œuvre élégante et générique dans Scala, telle que décrite dans les 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 :: _}
    }
}

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 contenant une table appelée " Alphabet " avec un seul champ de caractère & "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

Ceci renverra toutes les combinaisons de 3 lettres, quel que soit le nombre de lettres que vous avez dans le tableau & "Alphabet &"; (cela peut être 3, 8, 10, 27, etc.).

Si ce que vous voulez, ce sont toutes des permutations plutôt que des combinaisons (c.-à-d. vous voulez & "; ACB &" et & "ABC &"; compter comme différent, plutôt que de simplement apparaître une fois) supprimez simplement la dernière ligne (AND) et le tour est joué.

Post-édition: après avoir relu la question, je me rends compte que l’algorithme général est nécessaire, et pas seulement un algorithme spécifique pour le choix de 3 éléments. La réponse d'Adam Hughes est complète, malheureusement, je ne peux pas voter (pour le moment). Cette réponse est simple mais ne fonctionne que lorsque vous voulez exactement 3 éléments.

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

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));
}

Sortie:

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

Ici vous avez une version d'évaluation paresseuse de cet algorithme codé en C #:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

Et partie test:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

J'espère que cela vous aide!

J'ai utilisé un algorithme de permutation que j'ai utilisé pour le projet euler, en python:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

n<len(l)

vous devriez avoir toutes les combinaisons dont vous avez besoin sans répétition, en avez-vous besoin?

C’est un générateur, vous l’utilisez donc dans quelque chose comme ceci:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb

https://gist.github.com/3118596

Il existe une implémentation pour JavaScript. Il a des fonctions pour obtenir les k-combinaisons et toutes les combinaisons d'un tableau d'objets quelconques. Exemples:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}

Version de Clojure:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Disons que votre tableau de lettres ressemble à ceci: & "; ABCDEFGH &"; Vous avez trois index (i, j, k) indiquant les lettres que vous allez utiliser pour le mot actuel. Vous commencez par:

A B C D E F G H
^ ^ ^
i j k

D'abord, vous faites varier k, la prochaine étape est la suivante:

A B C D E F G H
^ ^   ^
i j   k

Si vous avez atteint la fin, vous continuez et vous modifiez j puis k à nouveau.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Une fois que vous avez atteint J, vous commencez également à varier.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

Basé sur https://stackoverflow.com/a/127898/2628125 , mais plus abstrait, pour toutes les tailles des pointeurs.

J'ai créé une solution dans SQL Server 2005 à cet effet et l'ai publiée sur mon site Web: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Voici un exemple pour montrer l'utilisation:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

résultats:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Voici ma proposition en C ++

J'ai essayé d'imposer le moins possible de restrictions sur le type d'itérateur, de sorte que cette solution suppose uniquement un itérateur, et qu'il peut s'agir d'un const_iterator. Cela devrait fonctionner avec n'importe quel conteneur standard. Dans les cas où les arguments n’ont pas de sens, std :: invalid_argumnent est lancé

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

Tout est dit et fait, voici le code O'caml pour cela. L'algorithme est évident à partir du code.

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

Voici un code que j'ai récemment écrit en Java, qui calcule et retourne toute la combinaison de & Quot; num & Quot; éléments de " outOf " éléments.

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

Une solution Javascript concise:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

Voici une méthode qui vous donne toutes les combinaisons de taille spécifiée à partir d'une chaîne de longueur aléatoire. Semblable à la solution de quinmars, mais fonctionne pour des entrées et des k variés.

Le code peut être modifié pour se terminer, c'est-à-dire "tamponner" à partir de l'entrée "abcd" w k = 3.

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

Sortie pour " abcde " ;:

abc abd abe acd ace ade bcd bce bde cde

J'ai écrit une classe pour gérer des fonctions communes permettant de travailler avec le coefficient binomial, qui correspond au type de problème auquel votre problème appartient. Il effectue les tâches suivantes:

Affiche tous les K-index dans un format agréable pour tout N, choisissez K dans un fichier. Les K-index peuvent être remplacés par des chaînes ou des lettres plus descriptives. Cette méthode rend la résolution de ce type de problème assez triviale.
Convertit les K-index en index correct d'une entrée de la table des coefficients binomiaux triée. Cette technique est beaucoup plus rapide que les anciennes techniques publiées qui reposent sur l'itération. Pour ce faire, il utilise une propriété mathématique inhérente au triangle de Pascal. Mon article en parle. Je crois que je suis le premier à découvrir et à publier cette technique, mais je peux me tromper.
Convertit l'index d'une table de coefficients binomiale triée en index K. correspondants.
Utilise la méthode Mark Dominus pour calculer le coefficient binomial, qui est beaucoup moins susceptible de déborder et fonctionne avec des nombres plus grands.
La classe est écrite en .NET C # et fournit un moyen de gérer les objets liés au problème (le cas échéant) à l'aide d'une liste générique. Le constructeur de cette classe prend une valeur bool appelée InitTable qui, lorsqu'elle est vraie, créera une liste générique destinée à contenir les objets à gérer. Si cette valeur est false, la table ne sera pas créée. La table n'a pas besoin d'être créée pour pouvoir exécuter les 4 méthodes ci-dessus. Des méthodes d'accès sont fournies pour accéder à la table.
Il existe une classe de test associée qui montre comment utiliser la classe et ses méthodes. Il a fait l’objet de tests approfondis dans 2 cas et aucun bogue connu.

Pour en savoir plus sur cette classe et télécharger le code, voir Tablizing The Binomial Coeffieicent .

Il ne devrait pas être difficile de convertir cette classe en C ++.

Algorithme:

Comptez de 1 à 2 ^ n.
Convertissez chaque chiffre en sa représentation binaire.
Traduisez chaque bit "actif" en éléments de votre ensemble, en fonction de la position.

En C #:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

Pourquoi ça marche?

Il existe une bijection entre les sous-ensembles d'un ensemble de n éléments et les séquences de n bits.

Cela signifie que nous pouvons déterminer le nombre de sous-ensembles en comptant les séquences.

Par exemple, les quatre éléments ci-dessous peuvent être représentés par {0,1} X {0, 1} X {0, 1} X {0, 1} (ou 2 ^ 4) séquences différentes.

Donc - tout ce que nous avons à faire est de compter de 1 à 2 ^ n pour trouver toutes les combinaisons. (Nous ignorons l'ensemble vide). Ensuite, traduisez les chiffres en leur représentation binaire. Remplacez ensuite les éléments de votre ensemble par des bits "actifs".

Si vous ne voulez que k résultats d’éléments, n’imprimez que lorsque k bits sont activés.

(Si vous voulez tous les sous-ensembles au lieu de k sous-ensembles de longueur, supprimez la partie cnt / kElement.)

(Pour la preuve, voir le didacticiel gratuit MIT Mathématiques pour l'informatique, Lehman et al, section 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/ 6-042j-mathématiques-pour-informatique-science-automne-2010 / lectures / )

Sautez dans le train et publiez une autre solution. Ceci est une implémentation Java générique. Entrée: (int k) est le nombre d'éléments à choisir et (List<T> list) est la liste de choix. Renvoie une liste de combinaisons (List<List<T>>).

public static <T> List<List<T>> getCombinations(int k, List<T> list) {
    List<List<T>> combinations = new ArrayList<List<T>>();
    if (k == 0) {
        combinations.add(new ArrayList<T>());
        return combinations;
    }
    for (int i = 0; i < list.size(); i++) {
        T element = list.get(i);
        List<T> rest = getSublist(list, i+1);
        for (List<T> previous : getCombinations(k-1, rest)) {
            previous.add(element);
            combinations.add(previous);
        }
    }
    return combinations;
}

public static <T> List<T> getSublist(List<T> list, int i) {
    List<T> sublist = new ArrayList<T>();
    for (int j = i; j < list.size(); j++) {
        sublist.add(list.get(j));
    }
    return sublist;
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow