Discussion :

[rafikindia]

Bonjour,

Dans le cadre d'un projet d'école je suis en train de me prendre la tete à développer l'algorithme suivant qui ressemble un peu au Loto.

Dans une LIST: a, b, c, d, e
et si number=1;
j'ai les possibilités suivantes: a, b, c, d, e

et si number= 2;
je dois avoir la combinaison de tout ces éléments en paires:
ex: ab, ac, ad, ae, bc, bd, be, cd, ce

et si number = 3
je dois avoir : abc, abd, abe, bcd, bce etc....

Auriez vous une piste vers laquelle je dois m'orienter pour le réaliser s'il vous plait.

[ttttnht]

Premiere vue tu as en entree:
une LIST
un CHIFFRE (represente le nombre d'elements de chaque liste)

Apres tu parcours ta LIST en fonction du CHIFFRE tu crees tes sous listes comme tu as dit dans tes exemples.

CHIFFRE = 1
LIST = a, b, c, d, e

Result = {a, b, c, d, e}

CHIFFRE = 2
LIST = a, b, c, d, e

Result = {ab, ac, ad, ae, bc, bd, be, cd, ce, de}
....

[Jidefix]

Effectivement il peut générer toutes les listes possibles mais ça va augmenter exponentiellement ça! Si le but est de générer une suite d'éléments uniques de la liste

Je conseillerai plutôt un algorithme du style:

Code :

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

1
2
3
4
5
 
Soit n le nombre d'éléments à choisir
Pour i de 1 à n
    Choisir un élément au pif dans la liste et le stocker dans le resultat
    Le retirer de la liste

Pour choisir un nombre aléatoirement en java, tu peux utiliser

Code :

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

1
2
 
int index = (int) Math.random()*n;

[LittleBean]

Si le but est de générer une suite d'éléments uniques de la liste

voir l'algo de Jidefix

Par contre pour avoir eu des projets similaires :p

Je pense que tu cherches à générer l'ensemble des combinaisons possible !

Dans ce cas tu te trouves faces à un problèmes dont la solution la plus simple est de passer par un algorithme récursif.

Tu as 3 étapes :
- la descente : comment faire pour décomposer ton problème en plus petit problèmes ? Il faut diminuer ton indice
=> dans ton cas cas une méthode qui prend en entrée un entier et une liste de char c(n,['a' ....'z'] ) = c(n-1, ['b'...'z']) .... c(n-1,['a'...'e','g'...'z'])

- la remontée : comment agréger les résultats des sous problèmes ?
=> dans ton cas il suffit de concaténer les chaînes avec la lettre retirée

- les cas terminaux : tout le boulot est là Comment on résout les problèmes simples ...
=> dans ton cas :
+ n=0 => renvoyer la liste
+ liste vide et n> 0 => erreur (tu demandes une combinaison de de n lettres et tu as moins de n lettres ...)

En gros c'est l'idée :p
Il existe d'autres solutions mais celle là me parait la plus élégante

Bon courage

[rafikindia]

Merci énormement pour votre aide.
J'ai réussi à traiter le cas pour le number = 1 et 2

Mais je ne vois pas du tout comment je pourrais faire pour les cas si number > 2.

En faites ce number sera fixer par l 'utilisateur.

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
 
private  Set<String> getCases(List<String> Obj, int Number) {
 
		Set<String> result= new HashSet<String>();
 
		if (Number == 1) {
			return Obj;
		}
		else {
			while (Obj.isEmpty() == false) {
 
				String firstElement = Obj.get(0);
				Obj.remove(firstElement);
 
				for (int j = 0; j < Obj.size(); j++) {
					String secondElement = Obj.get(j);	
					String res = firstElement+":"+secondElement;
					result.add(res);
				}
			}
		}
		return result;
 
	}

[rolfone]

un truc comme cela c'est pas optimiser mais ça marche

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
    public Set<String> generation(String alpha, int round) {
 
        Set<String> mesval = null;
        Set<String> mesnewval = new TreeSet<String>();
        if (round == 1) {
            mesval = new TreeSet<String>();
            for (char c : alpha.toCharArray()) {
                mesval.add(Character.toString(c));
            }
            return mesval;
        } else {
            mesval = this.generation(alpha, round - 1);
        }
 
        if(round > alpha.length()){
            return mesval;
        }
        for (String start : mesval) {
            for (char c : alpha.toCharArray()) {
                if (!start.contains(Character.toString(c))) {
                    mesnewval.add(start + c);
                }
            }
        }
 
        return mesnewval;
    }