Un arrangement plutot complexe

Version imprimable

30/01/2007, 15h52
champalaune

Un arrangement plutot complexe

Bonjour tout le monde,

Je cherche un algo efficace permettant de générer tous les arrangements possible d'un tableau de n case avec des elements pris parmis p entiers.
Exemple : Si je souhaite creer des tableaux de 2 cases pris parmis 4 elements,
on obtiendrait : 1,2 ; 1,3 ; 1,4 ; 2,1 ; 2,3 ; 2,4 ; 3,1 ; 3,2 ; 3,4 ; 4,1 ; 4,2 ; 4,3

En fait pour etre precis, je recherche quelque chose de recursif où l'on aurait pas besoin de stocker tous les tableaux en memoire (car avec stockage des tableaux, j'ai reussi a faire un petit truc mais c'est loin d'etre top...) En effet, je dois travailler avec 50 elements, et donc pour des tableaux de 7 cases, il faudrait deja 40 To de memoire ! :mouarf:
Si quelqu'un a une petite idée de comment faire...

Merci d'avance !

Ah... encore un arbre des possibles. C'est a la mode, ca fait mon 2eme en 2 jours :D. Y'aurait pas comme un sujet de TP commun :roll:

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
 
public class ArbreDesPossibles {
 
	private int size = 0;
	private int[] result = null;
	private List<Integer> elements;
 
	public ArbreDesPossibles(int size, int[] elts) {
		this.size = size;
		this.result = new int[size];
		this.elements = new ArrayList<Integer>();
		for(int i:elts) this.elements.add(i);
	}
 
	public void compute(int currentPos) {
 
		// la tableau est remplit
		if (currentPos==this.size) {
			print();
			return;
		}
 
		// essaye tous les cas possible
		for(int i=0;i<elements.size();i++) {
			// on retire le 1er element de la liste des elements restants
			Integer element = elements.remove(0);
			// on le met a la position courante dans le tableau 
			result[currentPos]=element;
			// on demande le calcul de la position suivante du tableau
			compute(currentPos+1);
			// on remet l'element qu'on avait retiré, au bout de la liste des elements restants
			elements.add(element);
		}
	}
 
	public void print() {
		System.out.println( Arrays.toString(this.result) );
	}
 
	public static void main(String[] args) {
		new ArbreDesPossibles(2,new int[]{1,2,3,4}).compute(0);
	}
}

Citation:

En effet, je dois travailler avec 50 elements, et donc pour des tableaux de 7 cases

La profondeur de recursion est egale a la taille du tableau, donc 7. C'est pas enorme :D. Enfin bon, j'ai quand meme optimisé le code pour limiter la consommation mémoire.

Citation:

Envoyé par pseudocode

Ah... encore un arbre des possibles. C'est a la mode, ca fait mon 2eme en 2 jours :D. Y'aurait pas comme un sujet de TP commun :roll:

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
 
public class ArbreDesPossibles {
 
	private int size = 0;
	private int[] result = null;
	private List<Integer> elements;
 
	public ArbreDesPossibles(int size, int[] elts) {
		this.size = size;
		this.result = new int[size];
		this.elements = new ArrayList<Integer>();
		for(int i:elts) this.elements.add(i);
	}
 
	public void compute(int currentPos) {
 
		// la tableau est remplit
		if (currentPos==this.size) {
			print();
			return;
		}
 
		// essaye tous les cas possible
		for(int i=0;i<elements.size();i++) {
			// on retire le 1er element de la liste des elements restants
			Integer element = elements.remove(0);
			// on le met a la position courante dans le tableau 
			result[currentPos]=element;
			// on demande le calcul de la position suivante du tableau
			compute(currentPos+1);
			// on remet l'element qu'on avait retiré, au bout de la liste des elements restants
			elements.add(element);
		}
	}
 
	public void print() {
		System.out.println( Arrays.toString(this.result) );
	}
 
	public static void main(String[] args) {
		new ArbreDesPossibles(2,new int[]{1,2,3,4}).compute(0);
	}
}

La profondeur de recursion est egale a la taille du tableau, donc 7. C'est pas enorme :D. Enfin bon, j'ai quand meme optimisé le code pour limiter la consommation mémoire.

Tu me diras quelle note tu as eu à la place de l'auteur du sujet ;)

01/02/2007, 12h48
champalaune

Merci avous, pour cette reponse si rapide !

J'vais quand meme faire ma petite enquete pour savoir si l'autre personne concerné ne fais pas partie de ma promo (ca serait pas cool qu'on m'accuse de plagia) :mouarf:

Bonne journee à tous !