Pb de permutation de n elements.

Version imprimable

01/08/2006, 11h48
sebastien2222

Pb de permutation de n elements.

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

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

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 :

Citation:

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:

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.

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:

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

01/08/2006, 14h44
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...
01/08/2006, 14h52
sebastien2222

en faite voila le resultat que je recuperes :

Citation:

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

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:

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ï

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:

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

01/08/2006, 15h29
sebastien2222

merci PRomu@ld et Jedai, je vais plutot partir sur ton code PRomu@ld (plus compatible avec du jdk 1.4 :lol: ) 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. :ccool:

Sébastien
01/08/2006, 16h44
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ï
01/08/2006, 17h24
PRomu@ld

Citation:

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 !
01/08/2006, 18h20
Jedai

Citation:

Envoyé par PRomu@ld

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ï
02/08/2006, 08h21
PRomu@ld

Citation:

Comment le clonage pourrait-il échouer ?

Plus de mémoire.

Citation:

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)
02/08/2006, 09h49
Jedai

Citation:

Envoyé par PRomu@ld

Plus de mémoire.

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

Citation:

Envoyé par PRomu@ld

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

Citation:

Envoyé par PRomu@ld

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ï
02/08/2006, 11h15
PRomu@ld

Citation:

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.

Citation:

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 !

Citation:

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.

Citation:

Envoyé par PRomu@ld

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é... :oops:

Citation:

Envoyé par PRomu@ld

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

Citation:

Envoyé par PRomu@ld

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:

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. :D

--
Jedaï

02/08/2006, 14h25
PRomu@ld

Citation:

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.

Citation:

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).
02/08/2006, 16h57
Jedai

Citation:

Envoyé par PRomu@ld

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ï
02/08/2006, 21h46
PRomu@ld

Citation:

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.
02/08/2006, 23h28
Jedai

Citation:

Envoyé par PRomu@ld

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ï
03/08/2006, 08h26
PRomu@ld

Citation:

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

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 ! :aie:
03/08/2006, 12h04
Jedai

Citation:

Envoyé par PRomu@ld

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

C'est ton "ça ne passe plus" qui m'a induit en erreur, si tu voulais juste indiquer qu'on aurait une légère réduction de performance (tout dépend de la fonction de hachage, mais ça ce n'est pas notre problème, c'est celui du programmeur qui doit l'implémenter si il utilise des types non-standard), tu aurais pu employer une expression plus modérée.

Certes il est probable que cette solution soit plus lente que ta solution de tableau, c'est le coût de la généricité ! Mais de toute façon depuis un certain temps on est plutôt dans l'abstrait, il est peu probable que le posteur originel utilise jamais cet algorithme pour générer des permutations pour un n élevé (et avec une complexité en O(n!), la croissance est exponentielle et totalement monstrueuse, donc les n raisonnables sont vraiment peu nombreux). Pour être tout à fait honnête, après benchmark la solution avec une LinkedList reste presque à égalité avec la solution LinkedHashSet avec n = 10 (3 628 800 permutations tout de même... et dans les 4 000 000 d'appels à apn(), 3 min sur mon PC (4 secondes en désactivant la sortie)), donc bon...
Si on a réellement besoin de tels n, il est sans doute bien plus raisonnable de faire cela en C, et avec une implémentation spécifique aux données qu'on va manipuler (ou éventuellement avec un générateur de fonction de hachage parfaite puisqu'ici on connaît l'ensemble des données possibles).

--
Jedaï
06/11/2008, 22h55
Kazuhiko$

Bonsoir,

Je rajoute une question sur ce topic car je ne veux pas ouvrir en un autre pour cette petite question: j'arrive à écrire l'algorithme de permutation avec une variable auxiliaire mais je ne comprend pas comment faire avec une fonction auxiliaire... (je suis sur Caml light)

si quelqu'un peut m'aider...
bonne soirée