Algorithme Combinaison

Fermé
robinho10 - 12 avril 2009 à 16:45
 Pseudo - 5 janv. 2013 à 13:05
Bonjour, je suis étudiant en première année de génie informatique et je suis coincé à trouver un solution à un algorithme ... L'exercice est le suivant :
Donnez un algorithme qui lis au clavier 21 nombres de 1 à 21 dans un tableau et qui nous permet de trouver toute les combinaisons possibles de 8 numéro existants dans ce tableau ...

ce qui veux dire par exemple pour 4 nombres allant de {1, 2, 3, 4} avec un choix de 2 numéros l'algorithme dois trouver comme résultats :
1 , 2
1 , 3
1 , 4
2 , 3
2 , 4
3 , 4

Le problème c'est comment faire comme cet exemple pour 21 numéros et un choix de 8 numéros et les afficher par la suite ...

Toutes propositions de solution est la bienvenue
Merci a vous tous d'avance ^^

2 réponses

Il faut utiliser une prog récursive et enlever les éléments une fois utilisés

en java ça donne ça

public static void main(String[] args) {

    ArrayList<Integer> nombres = new ArrayList<Integer>();

    for (int i = 0; i < 20; i++) {
      nombres.add(i);
    }
    List<List<Integer>> etablirCombinaison = etablirCombinaison(nombres, 8);

    for (List<Integer> combinaison : etablirCombinaison) {
      for (Integer i : combinaison) {
        System.out.print(i + " ");
      }

      System.out.println();
    }
  }

  private static List<List<Integer>> etablirCombinaison(ArrayList<Integer> nombres, int nb) {
    List<List<Integer>> combinaisons = new LinkedList<List<Integer>>();
    if (nb > 0) {
      ListIterator<Integer> listIterator = nombres.listIterator();

      while (listIterator.hasNext()) {
        Integer integer = (Integer) listIterator.next();
        listIterator.remove();

        List<List<Integer>> etablirCombinaison = etablirCombinaison(new ArrayList<Integer>(nombres), nb - 1);

        for (List<Integer> combinaison : etablirCombinaison) {
          combinaison.add(0, integer);
          combinaisons.add(combinaison);
        }
      }
    } else {
      combinaisons.add(new LinkedList<Integer>());
    }

    return combinaisons;
  }

                
1
Bonjour,
pourrais tu annoter ton code pour détailler le fonctionnement de chaque ligne stp, j'ai un peu de mal avec la récursivité et combinaison/combinaisons, même si globalement je comprends la démarche...
0