Pb de permutation de n elements.

**sebastien2222** · 01/08/2006, 11h48

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** · 01/08/2006, 12h44

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** · 01/08/2006, 14h17

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** · 01/08/2006, 14h44

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** · 01/08/2006, 14h52

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** · 01/08/2006, 14h55

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** · 01/08/2006, 15h19

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