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

[rafikindia]

Merci Rolfone,

Mais le problème c'est que mon Number peut aussi etre égale a "n".

D'après ton code cela ne marcherait que pour n = 1, 2 et 3

[dingoth]

Ce code marche pour n = 1...alphabet.size(). Il y a encore moyen de l'optimiser comme empêcher de calculer les fins de liste quand elles sont trop courtes par rapport à la longueur encore à produire, mais il est efficace.

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
import java.util.*;
 
public class Combi {
	public static void main(String[] args) {
		// Paramétrage
		List<String> alphabet = Arrays.asList("a", "b", "c", "d", "e");
		int length = 3;
 
		// Exécution
		List<String> result = combi(alphabet, length);
 
		// Affichage du résultat
		System.out.println(result);
	}
 
	// Démarrage de la boucle.
	static List<String> combi(List<String> alphabet, int length) {
		if (length < 0 || alphabet.length() < length) { throw new IllegalArgumentException(); }
		if (length == 0) {
			return Collections.emptyList();
		}
		List<String> result = new ArrayList<String>();
		combi2(alphabet, length, result, new StringBuilder());
		return result;
	}
 
	// Méthode de calcul, récursive.
	private static void combi2(List<String> alphabet, int length, List<String> result, StringBuilder buffer) {
		int bufferLength = buffer.length();
		for (int i = 0, size = alphabet.size(); i < size && length <= size - i; i++) {
			buffer.append(alphabet.get(i));
			if (length == 1) {
				result.add(buffer.toString());
			} else {
				combi2(alphabet.subList(i + 1, size), length - 1, result, buffer);
			}
			buffer.setLength(bufferLength);
		}
	}
}

Edit, j'ai rajouté la petite optimisation mentionnée en haut.