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

Art de la programmation informatique Volume 4 : Fascicule 3 en a une tonne qui pourrait correspondre à votre situation particulière mieux que ce 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 par 20 éléments dans votre ensemble 20 C ₃ \= 1140. Et si vous voulez itérer sur l'ensemble, il est préférable d'utiliser un algorithme de code gris modifié afin de ne pas les garder 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 en existe de nombreux pour différentes utilisations. Veut-on maximiser les différences entre les combinaisons successives ? minimiser ? et cetera.

Certains des articles originaux décrivant les codes gris :

1. Quelques chemins de Hamilton et un algorithme de changement minimal
2. Algorithme de génération de combinaisons d'échangeurs adjacents

Voici d'autres documents traitant de ce sujet :

1. Une mise en œuvre efficace de l'algorithme de génération de combinaisons d'échangeurs adjacents de Eades, Hickey et Read (PDF, avec code en Pascal)
2. Générateurs combinés
3. Aperçu des codes de Gray combinatoires (PostScript)
4. Un algorithme pour les codes Gray

Chase's Twiddle (algorithme)

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

L'algorithme de C ...

Index des combinaisons dans l'ordre lexicographique (algorithme Buckles 515)

Vous pouvez également référencer une combinaison par son index (dans l'ordre lexicographique). En réalisant que l'indice doit être une certaine quantité de changement de droite à gauche basée sur l'indice, 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} nous pouvons dire que la différence entre les éléments est de un et dans l'ordre et minimale. {1,2,4} a un changement et est lexicographiquement numéro 2. Ainsi, le nombre de "changements" dans la dernière place représente un changement dans l'ordre lexicographique. La deuxième place, avec un changement {1,3,4} a un changement mais compte pour plus de changement puisqu'elle est à la deuxième place (proportionnel au nombre d'éléments dans l'ensemble original).

La méthode que j'ai décrite est une déconstruction, car il semble que, de l'ensemble à l'indice, il faille faire l'inverse - ce qui est beaucoup plus délicat. Voici comment Boucles résout le problème. J'ai écrit quelques C pour les calculer J'ai utilisé l'indice des ensembles plutôt qu'une plage de chiffres pour représenter l'ensemble, de sorte que nous travaillons toujours à partir de 0...n. Note :

1. Comme les combinaisons ne sont pas ordonnées, {1,3,2} = {1,2,3} -- nous les ordonnons pour être lexicographiques.
2. Cette méthode a un 0 implicite pour commencer le jeu pour la première différence.

Index des combinaisons dans l'ordre lexicographique (McCaffrey)

Il y a une autre façon Le concept est plus facile à comprendre et à programmer, mais il ne bénéficie pas des optimisations de Buckles. Heureusement, il ne produit pas non plus de combinaisons dupliquées :

L'ensemble qui maximise où .

Par exemple : 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1) . Donc, la 27ème combinaison lexicographique de quatre choses est : {1,2,5,6}, ce sont les index de l'ensemble que vous voulez regarder. L'exemple ci-dessous (OCaml), nécessite choose fonction, de gauche à droite :

(* 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 (un plus général) des combinaisons globales de dossiers. Ils sont aussi rapides que possible, ayant la complexité O( n C _k ). La consommation de mémoire est limitée par 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, en partant de l'état initial. Puisque nous devons faire passer l'état entre différents états, nous n'utiliserons pas la boucle for, mais plutôt la récursion,

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

Answer 2

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 :

123
124
125
134
135
145
234
235
245
345

Answer 3

Solution courte en java :

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]

Answer 4

Puis-je présenter ma solution récursive 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é.

Answer 5

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

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

D'abord vous faites varier k, donc l'étape suivante ressemble à ça :

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

Si vous avez atteint la fin, vous continuez et faites varier 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 G, vous commencez également à faire varier i.

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

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

Écrit en code, 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]);
        }
    }
}