Discussion :

[nadjim]

bonjour à tous

J'ai besoin de créer une fonction qui me sortent les combinaison d'un tableau de taille n. Je viens de faire quelques essais, et j'ai réussi à écrire le code au dessous. J'ai compris comment faire pour p = 1, 2, 3, 4 ... mais j'aimerai généraliser cette fonction. Et quelque soit la valeur de p, pouvoir trouver toutes les combinaisons possibles.

Merci d'avance
Code C# :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
            int n = 5;
            int p;
            //essai de C1,5
            p = 1;
            for (int i = 1; i <= n - p + 1; i++)
            {
                Console.WriteLine(i);
            }
            //essai de C2,5
            p = 2;
            for (int i = 1; i <= n - p + 1; i++)
            {
                for (int j = i+1; j <= n - p + 2; j++)
                {
                    Console.WriteLine("{0}{1}", i, j);
                }
            }
            //essai de C3,5
            p = 3;
            for (int i = 1; i <= n - p + 1; i++)
            {
                for (int j = i+1; j <= n - p + 2; j++)
                {
                    for (int k = j+1; k <= n - p + 3; k++)
                    {
                        Console.WriteLine("{0}{1}{2}", i, j, k);
                    }
                }
            }
            //essai de C4,5
            p = 4;
            for (int i = 1; i <= n - p + 1; i++)
            {
                for (int j = i + 1; j <= n - p + 2; j++)
                {
                    for (int k = j + 1; k <= n - p + 3; k++)
                    {
                        for (int l = k + 1; l <= n - p + 4; l++)
                        {
                            Console.WriteLine("{0}{1}{2}{3}", i, j, k, l);
                        }
                    }
                }
            }

[Zavonen]

Tu as des réponses en langage python, à adapter donc:
Coefficients Cp,n

[Jean Dumoncel]

Bonjour,

Une solution en utilisant un algorithme récursif (a adapter pour le C#):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fonction permutation(tableau,p,n)
 
si longueur(tableau)==p // Condition d'arret
    afficher(tableau)
sinon
    si est_vide(tableau) // Initialisation si le tableau ne contient pas d'élément
        pour k de 1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tableau,k),p,n)
        finpour
    sinon
        pour k de derniere_valeur(tableau)+1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tableau,k),p,n)
        finpour
    finsi
finsi

Edit : remplacement de tab par tableau

[nadjim]

Bonjour,

Une solution en utilisant un algorithme récursif (a adapter pour le C#):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fonction permutation(tableau,p,n)
 
si longueur(tableau)==p // Condition d'arret
    afficher(tableau)
sinon
    si est_vide(tableau) // Initialisation si le tableau ne contient pas d'élément
        pour k de 1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tab,k),p,n)
        finpour
    sinon
        pour k de derniere_valeur(tableau)+1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tab,k),p,n)
        finpour
    finsi
finsi

Je te remercie mais j'aimerai bien avoir un algorithme qui ne soit pas récursif et je ne suis pas spécialement doué pour passer un algorithme récursif en itératif. Et les exemples en pythons sont récursifs eux aussi et par ailleurs je ne comprend rien à la syntaxe du python.

[mosto]

Bonjour,

Une solution en utilisant un algorithme récursif (a adapter pour le C#):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fonction permutation(tableau,p,n)
 
si longueur(tableau)==p // Condition d'arret
    afficher(tableau)
sinon
    si est_vide(tableau) // Initialisation si le tableau ne contient pas d'élément
        pour k de 1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tab,k),p,n)
        finpour
    sinon
        pour k de derniere_valeur(tableau)+1 à n-(p-longueur(tableau)-1)
            permutation(ajoute_element(tab,k),p,n)
        finpour
    finsi
finsi

c'est pas très clair ton algo. ta fonction permutation prend comme premier paramètre un tableau mais tu appelles ta fonction permutation(ajoute_element... et là tu passes une fonction

[Jean Dumoncel]

J'ai édité mon post car j'avais des noms de variables "tab" au lieu de "tableau" qui traînait dans mon code.

L'algorithme suppose que la taille de"tableau" puisse être modifiée. ajoute_element(tableau,k) renvoie un tableau avec une case en plus que "tableau" (et cette case contiendra k), donc le premier argument dans permutation(ajoute_element(tableau,k),p,n) est bien un tableau. Après le code dépend du langage et de la structure utilisée...

[pseudocode]

[FAQ] Détermination de combinaisons

[Onimaru]

Voici une solution qui ne change pas la taille du tableau mais récursive :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
procédure Combinaisons(var Tableau : Tab; Niveau: entier)
var I : entier
début
 si Niveau = H(Tableau) + 1 alors
  Afficher(Tableau)
 sinon
  pour I := Niveau à H(Tableau) faire
   Permuter(Tableau, Niveau, I)
   Combinaisons(Tableau, Niveau + 1)
   Permuter(Tableau, Niveau, I)
  fpour
 fsi
fin

H(Tableau) renvoie l'indice du dernier élément tableau (High).
L'appel se fait par Combinaisons(a), a = l'indice du premier élément du tableau (Low).

Toutes les combinaisons possibles sont affichées mais pas forcément dans l'ordre.