Discussion :

[sebastien2222]

bonjour a tous,

apres avoir effectué qq recherches sur le web et sur le forum, je seche complement sur un petit probleme de permutation.

Alors voilà, je dispose de n elements (de 1 à n) et je souhaiterais obtenir si n vaut 3 les elements suivants :

123
132
231
213
312
321

j'ai trouvé le topic suivant (en delphi) mais n'étant débutant en programmation (pour l'instant je ne "maitrise" que java) je ne comprends pas comment fonctionne la chose et souhaiterais qu'une ame charitable m'explique comment faire.

http://www.developpez.net/forums/sho...p=18302#372929

merci d'avance pour vos conseils.

Sébastien

[PRomu@ld]

Si je comprend bien, il te faut la procédure suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
procedure anp(n, p, liste)
 
    variable k : entier
 
    si p = 0 alors
       begin
       affiche chaine
       on sort de la procedure
       end
 
    pour k valant 1 à n faire
           si la liste ne contient pas l'élément numéro k 
          alors anp(n, p-1, liste + {élément numéro k});

Ici, n est le nombre de symboles de ta permutation (c'est 3 dans l'exemple que tu as donné)

p est le nombre d'éléments restant à permuter (au début c'est donc n)

liste est une liste (éventuellement vide) qui contient la permutation actuelle.

Le principe est le suivant :

- S'il n'y a plus d'élément à permuter alors c'est qu'on a fini et qu'il fait afficher la liste. (c'est le cas p = 0)

- S'il reste des élements non utilisés pour la permutation (on a donc pas utilisé tous les symboles pour la permutation), il faut donc trouver toutes les permutation restantes.

Pour trouver toutes les permutation restantes, il faut rappeler la fonction avec une liste ajoutée d'un symbole qui n'est pas encore dans la liste.

Un exemple avec n = 2 du déroulement :

AnP(2,2, [] )
-> comme p != 0 on fait ceci :
AnP(2,1,[1]) -- On ajoute 1 à la liste puisqu'il n'est pas dedans
AnP(2,1,[2]) -- On ajoute 2 à la liste puisqu'il n'est pas dedans

On traite donc les appels récursifs :
AnP(2,1,[1])
-> P n'est toujours pas nul alors on fait ceci :
AnP(2,0,[1,2])
-- On effectue pas l'appel AnP(2,0,[1,1]) car 1 est déjà dans la liste.

AnP(2,1,[2])
-> P n'est pas égal à 0 alors :
AnP(2,0,[2,1]
-- On effectue pas l'appel AnP(2,0,[2,2]) car 2 est déjà dans la liste.

On effectue les appels suivants :
AnP(2,0,[1,2])
-> P est nul, il faut afficher la liste et quitter.
[1,2]

AnP(2,0,[2,1])
-> P est nul, on affiche la liste.
[2,1]

Voilà, si tu veux en résumé ce qui se passe ça donne çà :

Code :

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

1
2
3
4
5
6
7
AnP(2,2,[])
     AnP(2,1,[1])
          AnP(2,0,[1,2])
               [1,2]
     AnP(2,1,[2])
          AnP(2,0,[2,1])
               [2,1]

Voilà, si tu as d'autres questions, n'hésite pas.

[sebastien2222]

merci pour vos préciseuses infos j'ai réalisé les fonctions mais cela ne fonctionne pas : le resultat que je recupere est [1,2] avec n et p = 2.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
import java.util.ArrayList;
import java.util.List;
 
 
public class permut 
{
 
	public static void main(String[] file)
	{
 
		List list_temp = new ArrayList();
 
		int n =2;
		int p =2;
		System.out.println("-> anp("+n+", "+p+", list)");
		anp(n,p, list_temp);		 
 
	}
 
 
	public static void anp(int n, int p, List list_temp)
	{
 
 
		if (p==0)
		{
 
			for (int i=0;i<list_temp.size();i++)
			{				
				System.out.println("-> "+list_temp.get(i));
			}
 
			System.out.println("-> Shutdown");
 
 
		}
 
		for (int i=1;i<=n;i++)
		{
 
			if (Search (list_temp,i)==false)
			{					
				String temp=Integer.toString(i);
				list_temp.add(temp);
 
				System.out.println("-> anp("+n+", "+p+", list)");
				anp(n, p-1, list_temp);
			}				
 
		}		
 
 
	}
 
	public static boolean Search(List list_temp, int k)
	{
		boolean result = false;
		String temp=Integer.toString(k);
 
		for (int i=0;i<list_temp.size();i++)
		{			
			if (list_temp.get(i).toString()==temp)
			{
				result = true;
				i = list_temp.size();
			}
		}
 
 
 
		return result;
	}

[PRomu@ld]

C'est surement un problème d'implémentation car j'utilise le même algo pour un programme en C, je regarde ton code...

[sebastien2222]

en faite voila le resultat que je recuperes :

anp(2, 2)

anp(2, 2)
----> list de 0 = 1

anp(2, 1)
----> list de 0 = 1
----> list de 1 = 2
-> 1
-> 2
-> fin de lecture

[Jedai]

Tu oublies qu'en Java les objet sont passés par référence, donc dans tout ton programme il n'y a qu'une seule liste...
Aussi il faut que tu corriges légèrement l'algorithme pour en tenir compte :

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
 
package fr.jedai.permutations;
 
import java.util.LinkedList;
 
public class Permutation<T> {
 
	private LinkedList<T> permutation;
	private T elts[];
 
	public Permutation(T elts[]){
		permutation = new LinkedList<T>();
		this.elts = elts;
	}
 
	public static void main(String[] file) {
 
		int p = 3;
		Integer[] list = {1, 2, 3};
		Permutation perm = new Permutation<Integer>(list);
 
		System.out.print("-> anp( n = " + list.length + ", p = " + p + ", liste = [");
		for (Integer elt : list) {
			System.out.print("{" + elt + "}");
		}
		System.out.println("])");
		perm.anp(p);
		System.out.println("-> Shutdown");
 
	}
 
	public void anp(int p) {
 
		if (p == 0) {
			System.out.print("-> [");
			for (T elt : permutation) {
				System.out.print("{" + elt + "}");
			}
			System.out.println("]");
			return;
		}
 
		for (T elt : elts) {
			if ( ! permutation.contains(elt) ) {
				permutation.addFirst(elt);
				anp(p - 1);			
				permutation.removeFirst();
			}
		}
	}
 
}

--
Jedaï

[PRomu@ld]

Jedai a répondu avant moi, mais effectivement, ton problème vient bien du passage des arguments.

J'avais une autre méthode qui reposait essentiellement sur ton code :

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
 
import java.util.ArrayList;
 
 
public class permut 
{
 
	public static void main(String[] file)
	{
 
		ArrayList list_temp = new ArrayList();
 
		int n =2;
		int p =2;
		System.out.println("-> anp("+n+", "+p+","+list_temp+")");
		anp(n,p, list_temp);		 
 
	}
 
 
	public static void anp(int n, int p, ArrayList list_temp)
	{
		if (p==0)
		{
			System.out.println(list_temp);
			System.out.println("-> Shutdown");
			return;
		}
 
		for (int i=1;i<=n;i++)
		{
 
			if ( ! list_temp.contains(Integer.toString(i)) )
			{	
				String temp=Integer.toString(i);
				ArrayList tmp = (ArrayList)list_temp.clone();
				tmp.add(temp);			
 
				System.out.println("-> anp("+n+", "+p+","+list_temp+")");
				anp(n, p-1, tmp );
			}			
		}		
	}
}

[sebastien2222]

merci PRomu@ld et Jedai, je vais plutot partir sur ton code PRomu@ld (plus compatible avec du jdk 1.4 ) mais merci qd meme Jedai !

merci d'avoir pris un peu de votre temps pour m'eclairer et bonne fin de journée a vous deux.

Sébastien

[Jedai]

Néanmoins la méthode de PRomu@ld implique de créer un ArrayList par apn... ce qui fait vite beaucoup, sachant que la création d'objet n'est jamais gratuite, il serait préférable d'utiliser mon interprétation, quitte à garder le code de PRomu@ld par ailleurs.
Notez que dans un langage fonctionnel la question ne se poserait pas, car le partage des données serait implicite.

--
Jedaï

[PRomu@ld]

Néanmoins la méthode de PRomu@ld implique de créer un ArrayList par apn... ce qui fait vite beaucoup, sachant que la création d'objet n'est jamais gratuite, il serait préférable d'utiliser mon interprétation, quitte à garder le code de PRomu@ld par ailleurs.

Oui, je suis tout à fait d'accord, mon code fait assez "porc", et ne devrait pas être utilisé en condition réelles ... (je n'utilise que très rarement java ...)

De plus aucun test n'est effectué si le clonage échoue, à prendre avec beaucoup de précautions !

[Jedai]

De plus aucun test n'est effectué si le clonage échoue, à prendre avec beaucoup de précautions !

Comment le clonage pourrait-il échouer ?

Par ailleurs, un rapide calcul nous montre que le nombre d'appel à apn() (et donc le nombre de liste créées) est à peu près en O(n!), ce qui est assez important...

--
Jedaï

[PRomu@ld]

Comment le clonage pourrait-il échouer ?

Plus de mémoire.

Par ailleurs, un rapide calcul nous montre que le nombre d'appel à apn() (et donc le nombre de liste créées) est à peu près en O(n!), ce qui est assez important...

Ca n'est pas à peut près, c'est exactement n!, et c'est tout à fait normal : il s'agit du nombre de permutation de n nombres.

Mais nous sommes d'accord, créer autant de liste à chaque fois n'est pas forcément une bonne idée. D'ailleur une liste ici n'est pas forcément une bonne idée (l'implémentation que j'ai en C utilise un tableau)

[Jedai]

Plus de mémoire.

Java n'est-il pas censé protester dans ce cas ?

Ca n'est pas à peut près, c'est exactement n!, et c'est tout à fait normal : il s'agit du nombre de permutation de n nombres.

Pas d'accord : c'est exactement :
somme( n! / (n-k)!, k, 1, p ) (pour k allant de 1 à p)
On ne calcule pas les permutations de n nombres, mais les permutations de p éléments parmi n éléments, de plus apn() est appelé également pour toutes les permutations de k éléments (k < p) parmi n avec notre algorithme.
Mais avec p = 1 par exemple, on est en O(n), pas vraiment du O(n!)... On n'est en O(n!) qu'en supposant que p varie linéairement avec n. Si p reste constant, on est en O(n^p).

Mais nous sommes d'accord, créer autant de liste à chaque fois n'est pas forcément une bonne idée. D'ailleur une liste ici n'est pas forcément une bonne idée (l'implémentation que j'ai en C utilise un tableau)

Une liste est parfaite pour représenter un permutation avec cet algorithme. Mais peut-être serait-il préférable d'utiliser également un Set pour accélérer la vérification d'appartenance à moins qu'on ne trouve moyen d'éviter totalement celle-ci (en changeant la représentation des éléments de sorte qu'on puisse retirer les éléments déjà utilisés).

--
Jedaï

[PRomu@ld]

Java n'est-il pas censé protester dans ce cas ?

Si, il va nous jeter avec une exception, et comme elle n'est pas capturée, elle va planter le programme.

Pas d'accord : c'est exactement :
somme( n! / (n-k)!, k, 1, p ) (pour k allant de 1 à p)

Je parlais de ce qui était demandé : les permutations, tu parles ici d'arrangement.

La permutation, c'est l'arrangement de n éléments d'un ensemble à n élement (on l'appelle d'ailleurs n-arrangement).

En reprenant la formule générale du nombre d'arrangement de p élement dans un ensemble à n élements on a donc :

n! / (n - p) !

Avec n = p on a donc bien n!

Nous ne parlions pas de la même chose, c'est tout !

Mais peut-être serait-il préférable d'utiliser également un Set pour accélérer la vérification d'appartenance

Un HashSet accélèrerait les recherches mais augmenterait le temps d'ajout, donc l'un dans l'autre ça compense peut être.

D'autres structures de données peuvent peut-être être plus performantes, l'idéal serait un temps d'ajout de l'ordre de O(1) et un temps de recherche de O(1).

Avec un tableau ça peut être possible. Pour le cas des permutations de nombres ou de lettres ça ne devrait pas poser de soucis.

[Jedai]

Je parlais de ce qui était demandé : les permutations, tu parles ici d'arrangement.

La permutation, c'est l'arrangement de n éléments d'un ensemble à n élement (on l'appelle d'ailleurs n-arrangement).

En reprenant la formule générale du nombre d'arrangement de p élement dans un ensemble à n élements on a donc :

n! / (n - p) !

Avec n = p on a donc bien n!

Nous ne parlions pas de la même chose, c'est tout !

Effectivement, je me suis concentré sur le code (qui réalise des arrangements) et je n'ai pas fait attention au vocabulaire employé...

Un HashSet accélèrerait les recherches mais augmenterait le temps d'ajout, donc l'un dans l'autre ça compense peut être.

Pas vraiment : pour de faibles valeur de p peut-être, mais asymptotiquement, on aurait un apn en O(n) plutôt qu'en O(np) (donc O(n²) pour des permutations). Il est probable qu'au final on constate un gain pour les grosses valeurs (et que la perte pour les petites valeurs reste négligeable).

D'autres structures de données peuvent peut-être être plus performantes, l'idéal serait un temps d'ajout de l'ordre de O(1) et un temps de recherche de O(1).

Avec un tableau ça peut être possible. Pour le cas des permutations de nombres ou de lettres ça ne devrait pas poser de soucis.

Tu veux dire avec un tableau de taille n où l'on stocke le rang d'un nombre i dans la permutation à l'index i ou -1 s'il n'y est pas ? C'est effectivement meilleur. Evidemment c'est un cas particulier (le cas général demanderait une table de hachage plutôt qu'un tableau), LinkedHashSet semble l'outil idéal pour traiter le cas général sans se compliquer la vie :

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
 
package fr.jedai.permutations;
 
import java.util.LinkedHashSet;
 
public class Permutation<T> {
 
	private LinkedHashSet<T> permutation;
	private T elts[];
 
	public Permutation(T elts[]){
		permutation = new LinkedHashSet<T>();
		this.elts = elts;
	}
 
	public static void main(String[] file) {
 
		int p = 3;
		Integer[] list = {1, 2, 3};
		Permutation perm = new Permutation<Integer>(list);
 
		System.out.print("-> anp( n = " + list.length + ", p = " + p + ", liste = [");
		for (Integer elt : list) {
			System.out.print("{" + elt + "}");
		}
		System.out.println("])");
		perm.anp(p);
		System.out.println("-> Shutdown");
 
	}
 
	public void anp(int p) {
 
		if (p == 0) {
			System.out.print("-> [");
			for (T elt : permutation) {
				System.out.print("{" + elt + "}");
			}
			System.out.println("]");
		}
 
		for (T elt : elts) {
			if ( ! permutation.contains(elt) ) {
				permutation.add(elt);
				anp(p - 1);			
				permutation.remove(elt);
			}
		}
	}
 
}

Ajout en O(1), test d'appartenance en O(1), suppression en O(1), à priori c'est un bon outil dans notre cas.

--
Jedaï

[PRomu@ld]

Tu veux dire avec un tableau de taille n où l'on stocke le rang d'un nombre i dans la permutation à l'index i ou -1 s'il n'y est pas ?

Oui, c'est comme ça que j'ai effectué pour mon programme C.

Ajout en O(1), test d'appartenance en O(1), suppression en O(1), à priori c'est un bon outil dans notre cas.

Oui, c'est parfait. Mais attention cependant, s'il y a collision entre deux valeurs, ça ne passe plus. (deux clés ont le même code de hachage).

[Jedai]

Oui, c'est parfait. Mais attention cependant, s'il y a collision entre deux valeurs, ça ne passe plus. (deux clés ont le même code de hachage).

Certes, mais c'est là une question plus fondamentale : autorise-t-on des éléments identiques dans la liste d'éléments, et dans ce cas comment les traiter ? Comme des éléments vraiment identiques et donc dont l'ordre n'a pas d'importance (ce qui modifie l'algorithme) ou comme des éléments ayant chacun leur identité propre, bien qu'elle ne soit pas explicitée, et donc dont l'ordre importe (algorithme inchangé, sauf que le HashSet ne marche plus).
J'ai implicitement pris pour hypothèse que l'on n'autoriserais pas les "vrais" doublons dans la liste d'éléments à permuter, il serait d'ailleurs plus logique d'utiliser un Set comme paramètre dans ce cas.

--
Jedaï

[PRomu@ld]

Certes, mais c'est là une question plus fondamentale : autorise-t-on des éléments identiques dans la liste d'éléments

Je ne parlais par forcément de doublons dans la liste des élements à permuter mais de doublons dans les code de hachage. Comme je ne connais pas les fonctions de hachage utilisée pour un HashSet, je ne sais pas si deux éléments n'auront pas le même code.

[Jedai]

Je ne parlais par forcément de doublons dans la liste des élements à permuter mais de doublons dans les code de hachage. Comme je ne connais pas les fonctions de hachage utilisée pour un HashSet, je ne sais pas si deux éléments n'auront pas le même code.

Tu sembles mal connaître les tables de hachage : deux éléments ayant le même code de hachage mais différent (au sens de equal() dans le cas de Java) ne sont pas confondus dans une table de hachage, heureusement !! Il existe plusieurs stratégie pour éviter cela, mais fondamentalement ça se résume à stocker toujours la clé avec la valeur à l'emplacement dans la table de hachage pointé par leur code, et à vérifier l'égalité des clés lorsqu'on doit faire un changement ou une consultation. Les éléments ayant le même code sont stockés soient dans une liste chaînées à l'emplacement pointé par leur code, soit de telle façon qu'il soit indiqué à cet emplacement qu'il y a une seconde valeur ayant le même code (avec une méthode pour retrouver cette seconde valeur, par exemple on va à l'emplacement suivant...).
Pour une petite explication sur les tables de hachage :
http://www.developpez.net/forums/sho...53&postcount=4

Une fonction de hachage qui donnerait un code différent à chaque élément d'un ensemble donné est dite parfaite, et est réalisable, mais uniquement si on connaît à l'avance les éléments de cet ensemble (ce qui n'est pas réalisable dans beaucoup d'application pratique).

--
Jedaï

[PRomu@ld]

Tu sembles mal connaître les tables de hachage

Encore une fois, il me semble que tu te méprends ! Je sais ce qu'est une table de hachage ( et heureusement ).

Nous parlions de performance sur notre algo d'arrangement (en fait de permutation), et nous cherchions une structure de donnée la plus adaptée pour minimiser les opérations de recherche/insertion/suppression.

Tu proposait donc une table de hachage et je te rappelais juste que la fonction de hachage devaient être bien choisie car si deux éléments ont même code de hachage nous allions avoir des pertes de performances.

Nous ne parlions pas du même sujet, voilà où était le problème !