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

Il s'agit d'un programme récursif qui génère des combinaisons pour nCk.Elements dans la collection sont supposés provenir 1 a n

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}

Answer 2

En VB.Net, cet algorithme collecte toutes les combinaisons de n nombres à partir d'un ensemble de nombres (PoolArray). Par exemple, toutes les combinaisons de 5 picks à partir de "8,10,20,33,41,44,47".

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
    If PicksIndex < PicksArray.Length Then
        For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
            PicksArray(PicksIndex) = PoolArray(i)
            CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
        Next
    Else
        ' completed combination. build your collections using PicksArray.
    End If
End Sub

        Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
        Dim nPicks as UInteger = 5
        Dim Picks(nPicks - 1) As UInteger
        CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

Answer 3

Le langage de programmation n'étant pas mentionné, je suppose que les listes sont également acceptables. Voici donc une version OCaml adaptée aux listes courtes (non récursive en queue). Étant donné une liste l d'éléments de tout et un nombre entier n il retournera une liste de toutes les listes possibles contenant n éléments de l si nous supposons que l'ordre des éléments dans les listes résultantes est ignoré, c'est-à-dire que la liste ['a';'b'] est la même que ['b';'a'] et sera signalée une fois. Ainsi, la taille de la liste résultante sera ((Liste.longueur l) Choisir n).

L'intuition de la récursion est la suivante : vous prenez la tête de la liste et faites ensuite deux appels récursifs :

• appel récursif 1 (RC1) : vers la queue de la liste, mais choisir n-1 éléments
• appel récursif 2 (RC2) : vers la queue de la liste, mais choisir n éléments

pour combiner les résultats récursifs, on multiplie par liste (attention au nom bizarre) la tête de la liste avec les résultats de RC1, puis on ajoute (@) les résultats de RC2. La multiplication de listes est l'opération suivante lmul :

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

lmul est implémenté dans le code ci-dessous comme

List.map (fun x -> h::x)

La récursion se termine lorsque la taille de la liste est égale au nombre d'éléments que vous voulez choisir, auquel cas vous renvoyez simplement la liste elle-même.

Voici donc une ligne de quatre en OCaml qui implémente l'algorithme ci-dessus :

    let rec choose l n = match l, (List.length l) with                                 
    | _, lsize  when n==lsize  -> [l]                                
    | h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)   
    | [], _ -> []

Answer 4

void combine(char a[], int N, int M, int m, int start, char result[]) {
    if (0 == m) {
        for (int i = M - 1; i >= 0; i--)
            std::cout << result[i];
        std::cout << std::endl;
        return;
    }
    for (int i = start; i < (N - m + 1); i++) {
        result[m - 1] = a[i];
        combine(a, N, M, m-1, i+1, result);
    }
}

void combine(char a[], int N, int M) {
    char *result = new char[M];
    combine(a, N, M, M, 0, result);
    delete[] result;
}

Dans la première fonction, m indique le nombre de personnes que vous devez choisir, et start indique la position dans le tableau à partir de laquelle vous devez commencer à choisir.

Answer 5

Et voici un Clojure qui utilise le même algorithme que celui que je décris dans mes OCaml réponse à la mise en œuvre :

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

Il propose trois façons de l'appeler :

(a) pour exactement n des éléments sélectionnés en fonction de la question posée :

  user=> (count (select 3 "abcdefgh"))
  56

(b) pour entre n1 y n2 les éléments sélectionnés :

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c) pour entre 0 et la taille de la collection d'articles sélectionnés :

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))