[Algo] Determination des combinaisons

Version imprimable

30/11/2006, 16h18
mavina

[Algo] Determination des combinaisons
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 :aie: : (code en java, mais mettez du pseudo langage si vous voulez ;))
Code:

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
30/11/2006, 16h26
Jean-Marc.Bourguet

http://www.developpez.net/forums/sho...d.php?t=228599
30/11/2006, 16h30
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 :aie:

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
30/11/2006, 16h56
millie
La version pour des entiers est la suivante :
Si c'était les combinaisons dont les éléments sont entre 0 et 2
Code:

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

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 :mrgreen: 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.
30/11/2006, 17h02
Jean-Marc.Bourguet

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

Permutations

Essayez cela:

Code:

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

03/12/2006, 18h38
Nemerle

euh... c'est un forum d'algorithmie, pas de java ;)
03/12/2006, 18h44
mavina

Salut,

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

Fred
03/12/2006, 19h56
Zavonen

Java, C, C++, Python, Scheme

Citation:

Envoyé par Nemerle

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.
03/12/2006, 21h09
thewho

Bonjour,

Citation:

Envoyé par Zavonen

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).
03/12/2006, 22h39
Zavonen

Citation:

Envoyé par thewho

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.
03/12/2006, 23h05
millie

Citation:

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

Justement, un algorithme est censé s'abstraire du langage dans lequel on l'utilise.

Citation:

Je voudrais simplement mettre l'accent sur le fait que les algorithmes sont inséparables des structures de données.

Un algorithme, c'est simplement une suite d'instruction compréhensible par un homme, et non pas forcement par une machine. Cela permet de faire des abstractions et donc de séparer l'algorithmique d'une quelconque implémentation. Evidemment, le jour où l'on codera en machine l'algorithme, il faudra déterminer une implémentation qui sera efficace pour le langage donnée.

Par exemple, un algorithme admettant une implémentation purement fonctionnel sera de très mauvaise qualité en langage C (dépassement de pile rapide) alors qu'il sera bon dans un langage comme CamL.

Citation:

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)

Justement non, car on peut se permettre d'écrire des choses en algorithmique qui ne sont pas bien définis (et dont la définition peut dépendre du langage et de l'implémentation), mais que nous, humains, compendrons.

Citation:

Mais chacun des langages réels invoqués me paraît plus clair que n'importe quel pseudo-code à la noix.

L'interêt d'un algorithme et qu'il est susceptible d'être compris par tout le monde (enfin, un minimum programmeur). Entre un algorithme et un code LISP, je prefère l'algorithme pour comprendre.

Citation:

Envoyé par Nemerle

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

Au passage, paraitrait-il que le terme algorithmie n'est pas français, mais que ce serait algorithmique :P
03/12/2006, 23h09
Nemerle

Citation:

Envoyé par Zavonen

On peut discuter de tout cela longuement sans aboutir à aucune conclusion définitive.

Quel pédantisme, c'est à pleurer :?

Citation:

Envoyé par Zavonen

Je voudrais simplement mettre l'accent sur le fait que les algorithmes sont inséparables des structures de données.

0/20, pas mieux. Je t'invite à aller voir la notion d'ontologie avec laquelle tu va essayer sous quelques années de travailler, visiblement sans succes.
03/12/2006, 23h10
Nemerle

Citation:

Envoyé par millie

Au passage, paraitrait-il que le terme algorithmie n'est pas français, mais que ce serait algorithmique :P

t'as raison millie, mais les veilles manieres sont tenaces ;)
04/12/2006, 09h36
Jean-Marc.Bourguet

Citation:

Envoyé par Zavonen

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.

La decouverte...
http://www.amazon.com/Algorithms-Str.../dp/0130224189

Citation:

Définir totalement et proprement un pseudo-code (il en existe de bons)

L'interet principal des pseudo-codes, c'est justement de ne pas etre defini totalement et de pouvoir se passer de ce qui n'est pas essentiel pour l'algorithme en question.
04/12/2006, 19h42
mavina

Bon, on recentre s'il vous plait, débat clos, si vous voulez en discuter, créez un topic et envoyez moi un mp, je déplacerai les messages ;)

Je reposterai des que j'aurai testé les solutions proposées.

Merci encore ;)

Fred