Discussion :

[mavina]

Bonjour,

J'ai actuellement un tableau d'entiers ne contenant aucun doublons puisqu"il va de 0 à n.
Mon but est de récupérer toutes les combinaisons possibles de tous ces entiers, sous forme de tableau.
exemple de tableau :
base { 0,1,2,3 }

J'ai fait le début mais je seche tres rapidement : (code en java, mais mettez du pseudo langage si vous voulez )

Code :

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

1
2
3
4
5
 
int[][] getCombinaisons(int[] base)
{
  int[][] resultat=new int[factoriele(base.length)][base.length];
}

Je sais que j'aurais factoriele(taille) resultats, mais je ne trouve pas d'algo pour trouver ceci.

Merci d'avance

Fred

[Jean-Marc.Bourguet]

http://www.developpez.net/forums/sho...d.php?t=228599

[mavina]

Bonjour,

J'ai bien vu ce topic lors de mes recherches, mais je ne comprends pas la manière de faire ni l'algorithme

Exemple :

en entrée :
{ 0, 1, 2}

en sortie :
{
{ 0, 1, 2},
{1, 0, 2},
{0, 2, 1},
{1, 2, 0},
{2, 0, 1},
{2, 1, 0},
}

Merci d'avance

Fred

[millie]

La version pour des entiers est la suivante :
Si c'était les combinaisons dont les éléments sont entre 0 et 2

Code :

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

1
2
3
4
5
Procédure genererSuivant(Permutation T)
  Si T[1] = 2
   evoluerRetenue(T,1)
  Sinon
   T[1]++;

Code :

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

1
2
3
4
5
6
Procédure evoluerRetenue(Permutation T, k)
 Tant que T[k] = 2 
    T[k] <- 0
    k++
 
 T[k]++

Donc ici, tu initialses T au début avec [0,0,0,0]

L'appel à : genererSuivant(T) te modifie T en [1,0,0,0],
l'appel suivant à : [2,0,0,0]
l'appel suivant à : [0,1,0,0]
l'appel suivant à : [1,1,0,0]...

Tu t'arrêtes quand tout est à 2. Dans l'algorithme, j'ai supposé le tableau infini (mais il faut s'arrêter quand tu en as assez)


Si tu renverses le tableau, tu vois que c'est de la forme :
0001 -> 0002 -> 0010 -> 0011. Tu vois que ça revient juste à additionner 1 à un nombre en base 3 C'est le principe que j'ai utilisé.


EDIT : arf, je viens de voir que tu devais ne pas avoir de doublons. Dans ce cas, il faudrait vérifier à chaque étape si il y a un doublon (passer au suivant) ou non. Mais peut être y a-til plus rapide comme méthode pour ce cas précis.

[Jean-Marc.Bourguet]

Il y a l'algo de Dijsktra que j'ai deja poste ici.

[Zavonen]

Essayez cela:

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
46
47
48
49
50
51
52
53
54
55
56
package javaapplication2;
 
import java.util.LinkedList;
 
 
 
 
public class Main {
 public static LinkedList Permutations (LinkedList Base)
{    LinkedList L=new LinkedList();// doit contenir la liste des permutations
     if (Base.size()==1) // cas terminal de la récursivité
     { 
     L.add(Base);
     return L;
     }
 else // cas d'une liste de longueur >1
 {   Object F= new Object();
     F=Base.getFirst(); // on récupère l'objet de tête
     LinkedList L1=new LinkedList();
     L1=(LinkedList) Base.clone();
     L1.removeFirst(); // on retire le premier élement
     LinkedList L2= new LinkedList();
     L2=Permutations(L1); // on obtient la liste des permutations de tous ceux qui restent
     LinkedList L3=new LinkedList(); // pour parcourir L2
     LinkedList L4=new LinkedList(); // pour insérer le premier élément
     for(int i=0;i<L2.size();i++)
     {L3=(LinkedList)(L2.get(i)); 
      for(int j=0;j<Base.size();j++)
     {L4=(LinkedList) L3.clone(); // On fait une copie de L3
      L4.add(j,F); // auquel on ajoute la tête de Base au bon endroit
     L.add(L4.clone()); // et on vieznt enrichir L de ce nouveau résultat
     }
    }
      return L;
 }
 }
 
 
    /** Creates a new instance of Main */
    public Main() {
    }
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        LinkedList Base= new LinkedList ();
        Base.add('a');
        Base.add('b');
        Base.add('c');
        System.out.println(Permutations(Base));
 
    }
 
}

[Nemerle]

euh... c'est un forum d'algorithmie, pas de java

[mavina]

Salut,

Merci, j'essaie des que possible et je vous tiens au courant

Fred

[Zavonen]

euh... c'est un forum d'algorithmie, pas de java

Je ne roule pas pour Java !
Mais chacun des langages réels invoqués me paraît plus clair que n'importe quel pseudo-code à la noix.
Quant à parler d'algorithmes en langage de salon entre la poire et le fromage c'est décoratif, mais pas productif.

[thewho]

Bonjour,

Je ne roule pas pour Java !
Mais chacun des langages réels invoqués me paraît plus clair que n'importe quel pseudo-code à la noix.
Quant à parler d'algorithmes en langage de salon entre la poire et le fromage c'est décoratif, mais pas productif.

1) tous les pseudos codes utilisés pour écrire des algorithmes ne sont pas "à la noix"

2) penser un algorithme en fonction d'un langage est mauvais : le résultat dépend trop d'une implémentation, et surtout dépend de la maîtrise qu'on a du langage en question, ce qui, très souvent, conduit à un résultat non optimum, ce qui n'est pas forcément catastrophique, mais également parfois faux, car si on ne connaît pas suffisamment le langage, il arrive qu'on ne réfléchisse pas assez, voire ou pas du tout, à ce qu'il faudrait faire, la réflexion se limitant souvent dans ce cas à ce que l'on sait faire.

3) si tu penses que tout cela "est décoratif", et que par conséquent tu passes outre à l'impératif de correctement préparer l'algorithme pour le programme à faire, alors il y a pas mal de chances pour que ta progression en programmation culmine assez rapidement, car ta réflexion sera bridée par tes connaissances d'un (ou plusieurs) langage(s).

[Zavonen]

Bonjour,

1) tous les pseudos codes utilisés pour écrire des algorithmes ne sont pas "à la noix"

2) penser un algorithme en fonction d'un langage est mauvais : le résultat dépend trop d'une implémentation, et surtout dépend de la maîtrise qu'on a du langage en question, ce qui, très souvent, conduit à un résultat non optimum, ce qui n'est pas forcément catastrophique, mais également parfois faux, car si on ne connaît pas suffisamment le langage, il arrive qu'on ne réfléchisse pas assez, voire ou pas du tout, à ce qu'il faudrait faire, la réflexion se limitant souvent dans ce cas à ce que l'on sait faire.

3) si tu penses que tout cela "est décoratif", et que par conséquent tu passes outre à l'impératif de correctement préparer l'algorithme pour le programme à faire, alors il y a pas mal de chances pour que ta progression en programmation culmine assez rapidement, car ta réflexion sera bridée par tes connaissances d'un (ou plusieurs) langage(s).

On peut discuter de tout cela longuement sans aboutir à aucune conclusion définitive. Je voudrais simplement mettre l'accent sur le fait que les algorithmes sont inséparables des structures de données. dès lors qu'un langage est riche en structure de données (Python-Java par exemple qui proposent tout un ensemble de collections prêtes à l'emploi) les algorithmes sont faciles à décrire. Ils deviennent beaucoup plus complexes avec des langages de bas niveau (type C ou Fortran). Définir totalement et proprement un pseudo-code (il en existe de bons) revient pour moi à recréer un langage de programmation (réinventer la roue). Cependant il est vrai que les algos sont bien évidemment et fort heureusement indépendants des langages. On s'éloigne du sujet. Salut.