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


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

Supposons que vous fournissiez un tableau de 8 lettres et que vous vouliez en sélectionner 3 lettres. Alors vous devriez obtenir:

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

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


500


origine


Réponses:


Art de la programmation informatique Volume 4: Fascicule 3 a une tonne de ceux qui pourraient mieux correspondre à votre situation particulière que je ne le 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 avec 20 éléments dans votre set - 20C3 = 1140. Et si vous voulez parcourir l'ensemble, il est préférable d'utiliser un algorithme de code Gray modifié de sorte que vous ne les conserviez pas tous en mémoire. Ceux-ci génèrent la combinaison suivante à partir du précédent et évitent les répétitions. Il y en a beaucoup pour différents usages. Voulons-nous maximiser les différences entre les combinaisons successives? minimiser? etc.

Certains des documents originaux décrivant les codes gris:

  1. Quelques chemins de Hamilton et un algorithme de changement minimal
  2. Algorithme de génération de combinaison d'échange adjacent

Voici d'autres articles sur le sujet:

  1. Une implémentation efficace de l'algorithme de génération de combinaison d'échange adjacent d'Eades, Hickey (PDF, avec code en Pascal)
  2. Générateurs Combinés
  3. Enquête sur les codes gris combinatoires (PostScript)
  4. Un algorithme pour les codes Gray

Twiddle de Chase (algorithme)

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

L'algorithme en C...

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

Vous pouvez également référencer une combinaison par son index (dans l'ordre lexicographique). En réalisant que l'index devrait être une certaine quantité de changement de droite à gauche en fonction de 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 {1,2,3} que nous pouvons dire que la différence entre les éléments est un et dans l'ordre et minime. {1,2,4} a un changement, et est lexicographiquement numéro 2. Donc le nombre de 'changements' à 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 car il est à la deuxième place (proportionnelle au nombre d'éléments dans l'ensemble d'origine).

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

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

Index des combinaisons en ordre lexicographique (McCaffrey)

Il y a autrement:, son concept est plus facile à saisir et à programmer, mais sans les optimisations des boucles. Heureusement, il ne produit pas non plus de combinaisons en double:

L'ensemble x_k...x_1 in N qui maximise i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1), où C(n,r) = {n choose r}.

À titre d'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 tout ensemble que vous voulez regarder. Exemple ci-dessous (OCaml), nécessite choose fonction, laissé 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)

368



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

Usage:

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

Résultat:

123
124
125
134
135
145
234
235
245
345

181



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é.


68



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]

64



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

A B C D E G G H
^ ^ ^
je j k

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

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

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

A B C D E G G H
^ ^ ^
je j k

A B C D E G G H
^ ^ ^
je j k

Une fois que vous avez atteint G, vous commencez aussi à varier.

A B C D E G G H
  ^ ^ ^
  je j k

A B C D E G G H
  ^ ^ ^
  je j k
...

Écrit dans le code ceci 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]);
        }
    }
}

58



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

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

Itérer ce qui précède pour chacun i dans l'ensemble.

Il est essentiel que vous choisissiez le reste des éléments plus grand que i, pour éviter la répétition. De cette façon, [3,5] sera choisi une seule 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.


45



J'ai trouvé ce fil utile et je pensais ajouter une solution Javascript que vous pouvez intégrer à Firebug. Selon 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");

La sortie devrait être la suivante:

abc
ab
ac
a
bc
b
c

23



En C ++, la routine suivante produira toutes les combinaisons de distance de longueur (first, k) entre la plage [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 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;
}

Cela imprimera les éléments suivants:

123
124
125
134
135
145
234
235
245
345

22