idée de l'algorithme

Version imprimable

Bonsoir,
j'ai ces 2 ArrayList
j ai du mal, a construire les ensembles suivant,
j'ai essayé d'imbriquer les boucles for, mais ça ne ressous pas mon problème.
Je ne vous demande pas d'écrire mon code.
Juste me donner une idée de l'algorithme, en francais

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
for(int f=0; f< chaine2b.size()-1; f++){
            	for(int g = f+1; g< chaine2b.size(); g++){
                   	String 	res = "";
                    res = var;
                    res += chaine2b.get(f);
                    res += chaine2b.get(g);
                    monSet.add(new String("" + res + ""));
            		System.out.println("res: " + res);
            		}
 
            }

resultat pour un ensemble a 3 elements

Code:

1
2
3
4
5
6
{0011,0100,1000}
{1100,0001,0010}
{0101,0010,1000}
{0110,0001,1000}
{1001,0010,0100}
{1010,0001,0100}

Je sais pas comment faire pour un ensemble à 4 elts

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
ArrayList1: [123]
ArrayList2: [14, 15, 24, 25, 34, 35, 45]
 
(123, 14, 15, 24)
(123, 14, 15, 25)
(123, 14, 15, 34)
(123, 14, 15, 35)
(123, 14, 15, 45)
 
(123, 15, 24, 25)
(123, 15, 24, 34)
...
 
(123, 24, 25, 34)
(123, 24, 25, 35)
..
(123,25, 34, 45)
...
(123, 34, 35, 45)

27/04/2009, 22h56
gifffftane

Heu... j'ai du mal à comprendre :cfou:

Pourrais-tu nous décrire le truc en français, sans algorithme ?
27/04/2009, 23h05
nypahe

ArrayList1: [123]
ArrayList2: [14, 15, 24, 25, 34, 35, 45]

Je souhaite à partir de ces 2 arrayList construire des ensembles à 4 elements
le premier ensemble est (123, 14, 15, 24)
le second (123, 14, 15, 25).
L'idée est de prendre, le premier de ArrayList1 et le composer avec 3 elts de ArrayList2,
Faire toutes les combinaisons de prendre un elt de ArrayList1, le composer avec 3 elts de ArrayList2, sans faire les repetition d'ensemble, et ayant composé avec tous les elements.
J'espere avoir été claire.
Merci d'avance

Toutes les combinaisons à un élément d'une liste : simple parcours de liste.

Toutes les combinaisons à 3 éléments d'une liste : ça fonctionne très bien avec 3 boucles imbriquées.
Toutes les combinaisons à 3 éléments d'une liste, avec des éléments différents, et en conservant l'ordre des éléments :
Code:

1 2 3 4 5 6 7 8 9 for (int i = 0 ; i < list.size() ; i++) { for (int j = (i+1) ; j < list.size() ; j++) { for (int k = (j+1) ; k < list.size() ; k++) { Object element1 = list.get(i); Object element2 = list.get(j); Object element3 = list.get(k); // ... } }
Toutes les combinaisons à 3 éléments d'une liste, avec des éléments éventuellement identiques, et en conservant l'ordre des éléments :
Code:

1 2 3 4 5 6 7 8 9 for (int i = 0 ; i < list.size() ; i++) { for (int j = (i) ; j < list.size() ; j++) { for (int k = (j) ; k < list.size() ; k++) { Object element1 = list.get(i); Object element2 = list.get(j); Object element3 = list.get(k); // ... } }
Toutes les combinaisons à 3 éléments d'une liste, avec des éléments éventuellement identiques, et sans conserver l'ordre des éléments :
Code:

1 2 3 4 5 6 7 8 9 for (int i = 0 ; i < list.size() ; i++) { for (int j = 0 ; j < list.size() ; j++) { for (int k = 0 ; k < list.size() ; k++) { Object element1 = list.get(i); Object element2 = list.get(j); Object element3 = list.get(k); // ... } }
Ça marche bien parce que tu veux 3 éléments (valeur fixe, codée en dur dans le programme). Si tu voulais pouvoir choisir "dynamiquement" le nombre d'éléments à sélectionner dans la liste, tu ne pourrais évidemment pas écrire des boucles imbriquées, ce serait plus compliqué et il faudrait sans doute passer par des fonctions récursives.

28/04/2009, 10h54
nypahe

Citation:

Envoyé par Astartee

Ça marche bien parce que tu veux 3 éléments (valeur fixe, codée en dur dans le programme). Si tu voulais pouvoir choisir "dynamiquement" le nombre d'éléments à sélectionner dans la liste, tu ne pourrais évidemment pas écrire des boucles imbriquées, ce serait plus compliqué et il faudrait sans doute passer par des fonctions récursives.

Bonjour,
Comment je pourrai programmer cette fonction récursive, pour éviter de faire plusieurs boucle for
Une pour une combinaison de 2 elts comme j ai fait précédemment, à 3 elts comme vous n'avez montrer
j'aurai à faire aussi une combinaison à 4 elt. donc pour éviter ces boucles, je pense que l'idée d'une fonction récursive, fera mieux l'affaire.
Merci d'avance pour l'aide
29/04/2009, 07h55
Astartee

Indices pour une fonction récursive qui liste toutes les combinaisons à n éléments d'une liste, avec des éléments différents, et en conservant l'ordre des éléments (1er cas dans mon post précédent) :

Ecris une fonction qui a la signature suivante (avec ce que tu veux à la place de T, ou en créant effectivement une fonction générique)

Code:

List<List<T>> maFonction(List<T> list, int n, int offset)

qui renvoie la liste des combinaisons (List<T>) de n éléments de la liste list à partir de l'indice offset.
Exemple : pour list=[a, b, c, d, e, f], n=2, offset=3 maFonction va renvoyer [[d, e], [d, f], [e, f]].
Pour obtenir "l'ensemble des combinaisons à n éléments de la liste list" il suffit évidemment d'appeler maFonction(list, n, 0).
Trouve un nom plus explicite que maFonction, bien sûr.

Pour n > (list.size()-offset) on lève une exception (impossible de trouver plus d'éléments qu'il n'y en a dans la sous-liste...).

Pour n = 0 on renvoie [[]] (la seule combinaison à 0 éléments est la liste vide).

Pour n > 0... ahah, on arrive au coeur du problème...
On parcourt la liste de l'indice offset à la fin de la liste, ce qui nous donne le premier élément de la combinaison, et on complète avec chacune des combinaisons à (n-1) éléments du reste (à partir de l'indice présent +1) de la liste (c'est donc là qu'on a un appel récursif).
Je ne sais pas si c'est très clair, mais en réfléchissant tu devrais déjà avoir compris le principe rien qu'avec la signature et la description de la fonction données plus haut ;)