Bonjour, 

Je commence à tout me mélanger dans l'énumération de combinaisons, et j'aurai besoin de votre aide. 

Voilà je dispose d'une liste de questions (disons question1 et question2). La question1 a 3 réponses possibles : A, B, ou C. La question2 a 4 réponses possibles : D, E, F ou G. Je voudrais énumérer la liste de toutes les combinaisons de réponses possibles : AD, AE, AF, AG, BD, BE, BF, BG, CD, CE, CF, CG. Pourriez-vous me dire si vous pensez à une méthode simple pour faire ça ? 

Merci à tous et bonne journée 

Bonjour, 

S'il ne peux y avoir que deux questions, ça va, deux boucles for et c'est réglé. Par contre s'il peut y en avoir plus, étant donnée qu'on ne peux pas connaître le nombre de questions (et donc pas savoir le nombre de boucle for que l'on doit imbriquer dans notre code), alors tu devras utiliser la récursivité.

akinatorus a écrit:

Bonjour, 

S'il ne peux y avoir que deux questions, ça va, deux boucles for et c'est réglé. Par contre s'il peut y en avoir plus, étant donnée qu'on ne peux pas connaître le nombre de questions (et donc pas savoir le nombre de boucle for que l'on doit imbriquer dans notre code), alors tu devras utiliser la récursivité.

La récursivité m'étais aussi venu à l'idée

Je suis du même avis pour la récursivité. Mon nombre de questions est variable, tout comme le nombre de réponses possibles. Je n'arrive pas à formuler correctement un algorithme pour résoudre mon problème

Et bien commence ton algorithme comme si tu avais un nombre fixe de réponses, et tu verras que tu pourras généraliser avec un nombre variable de réponses.

Mais il faut également que je parcours mon ensemble de questions et là je m'embrouille complètement.

Bonjour,

Pour rejoindre Pinguet62, je te conseille d'essayer de faire un exemple sur papier (ou plusieurs) et après je pense que l'algorithme devrait être plus clair pour toi. 

Bonjour, 

J'ai commencé à implémenter ma méthode pour obtenir toutes les combinaisons avec cette fonction : 

List<List<Object>> allAnswers = new ArrayList<List<Object>>();
        
        for (int i = 0; i < questions.size(); i++) {
            List<Object> answers = new ArrayList<Object>();
            for (int j = 0; j < questions.get(i).responses.size(); j++) {
                answers.add(questions.get(j).responses.get(i));
            }
            System.out.println("Answers : " + answers);
            allAnswers.add(answers);
        }
        
        System.out.println("All answers : " + allAnswers);
        return allAnswers;

Malheureusement ça ne couvre pas tous les cas, si je teste avec pour question1 comme réponses A ou B et pour question2 pour réponses C ou D, j'obtiens All answers : [[A, C], [B, D]]

Il ne doit pas manquer grand chose et j'imagine que c'est juste sous mes yeux mais je n'arrive pas à débloquer ça.

answers.add(questions.get(j).responses.get(i));

Tu as inversé le i et le j ?

aRaMinet a écrit:

answers.add(questions.get(j).responses.get(i));

Tu as inversé le i et le j ?

Utilise plutôt le foreach qui est plus joli, performant, et n'est pas une source de bug (comme celle-ci).

Si j'inverse le i et le j j'obtiens allAnswer : [[A, B],[C, D]], ce qui n'est pas ce que je souhaite malheureusement. 

J'ai essayé une nouvelle méthode : 

for (int i = 0; i < questions.size(); i++) {
            
            for (int j = 0; j < questions.get(i).responses.size(); j++) {
                List<Object> answers = new ArrayList<Object>();
                for (int k = 0; k < questions.size(); k++) {
                    answers.add(questions.get(k).responses.get(j));
                }
                allAnswers.add(answers);
                System.out.println("Answers : " + answers);
            }
            
        }

J'obtiens avec ceci allAnswers = [[A, C], [B, D], [A, C], [B, D]] ce qui est une bonne piste mais il me faudrait [A, D] et [B, C] au lieu d'une répétition. Je continue donc de chercher comment faire

Une solution, peut être pas la plus optimale:

D'abord je définis une classe Question, qui contient une liste de réponse et une référence vers la prochaine question:

public class Question
{
	
	private String text;
	
	private Question next = null;
	
	private List<Answer> answers = new LinkedList<Answer>();
	
	public Question(String text)
	{
		this.text = text;
	}
	
	public void setAnswers(Answer... answers)
	{
		for(Answer answer : answers)
		{
			this.answers.add(answer);
		}
	}
	
	public void setNextQuestion(Question next)
	{
		this.next = next;
	}
	
	public String getText()
	{
		return text;
	}
	
	public Question getNext()
	{
		return next;
	}
	
	public List<Answer> getAnswers()
	{
		return answers;
	}

}

Ensuite une classe Answer, toute simple:

public class Answer
{
	
	private String text;
	
	public Answer(String text)
	{
		this.text = text;
	}
	
	public String getText()
	{
		return text;
	}

	@Override
	public String toString()
	{
		return text;
	}

}

Dans le main je déclare mes questions et réponses et fait appel à une fonction récursive qui va te trouver toutes les réponses possibles:

public static void main(String[] args)
{
	Question q1 = new Question("Q1");
	Question q2 = new Question("Q2");
	Question q3 = new Question("Q3");
	
	Answer A = new Answer("A");
	Answer B = new Answer("B");
	Answer C = new Answer("C");
	Answer D = new Answer("D");
	Answer E = new Answer("E");
	Answer F = new Answer("F");
	Answer G = new Answer("G");

	q1.setAnswers(A, B, C);
	q1.setNextQuestion(q2);
	q2.setAnswers(D, E);
	q2.setNextQuestion(q3);
	q3.setAnswers(F, G);
	
	List<List<Answer>> answers = new LinkedList<List<Answer>>();
	findAnswers(q1, answers);
	System.out.println(answers);
}

La fonction en question:

public static List<List<Answer>> findAnswers(Question q, List<List<Answer>> answers)
{
	if(q == null)
	{
		return answers;
	}
	
	boolean start = answers.isEmpty();
	List<List<Answer>> temp = new LinkedList<List<Answer>>();
	
	for(Answer a : q.getAnswers())
	{
		if(start)
		{
			List<Answer> answerList = new LinkedList<Answer>();
			answerList.add(a);
			temp.add(answerList);
		}
		else
		{
			for(List<Answer> list : answers)
			{
				List<Answer> answerList = new LinkedList<Answer>();
				answerList.addAll(list);
				answerList.add(a);
				temp.add(answerList);
			}
		}
	}
	
	answers.clear();
	answers.addAll(temp);
	
	return findAnswers(q.getNext(), answers);
}

Et en sortie console j'obtiens:

[[A, D, F], [B, D, F], [C, D, F], [A, E, F], [B, E, F], [C, E, F], [A, D, G], [B, D, G], [C, D, G], [A, E, G], [B, E, G], [C, E, G]]

Hésites pas si tu as des questions

-
Edité par aRaMinet 28 juillet 2015 à 15:35:37

Merci beaucoup pour cette réponse finalement j'ai trouvé une méthode qui s'adapte bien à mon problème et à mes classes : 

private static List<List<HashMap<String, Object>>> getAllAnswersSeries(List<Question> questions) {
        
        List<List<String>> allCombinations = new ArrayList<List<String>>();
        allCombinations.add(new ArrayList<String>());
        
        for (Question question : questions) {
            List<List< String >> newAllCombinations = new ArrayList<List< String >>();
            for (String answer : question.responses) {
                for (List< String > combination : allCombinations) {
                    List< String > newCombination = new ArrayList< String >(combination);
                    newCombination.add(answer);
                    newAllCombinations.add(newCombination);
                }
            }
            allCombinations = newAllCombinations;
        }
        
        return allCombinations;
    }

Merci à tous pour votre aide :) 

-
Edité par Paulyne 29 juillet 2015 à 11:08:46