Générer tous les permutations admissibles

Signaler
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015
-
Messages postés
14790
Date d'inscription
vendredi 14 mars 2003
Statut
Modérateur
Dernière intervention
15 mai 2021
-
Salut tout le monde,

J'aimerai générer tous les permutations possibles d'un ensemble mais les permutations ne sont pas tous admissibles. Les permutations sont selon les combinaisons des permutations des sous ensembles.

Par exemple on a la liste suivante composée des sous ensembles: List = {(1,2),(3,4)}
les permutations admissibles sont : 1234/1243/2134/2143/3412/4312/3421/4321
les permutations suivantes ne sont pas admissibles : 1423/3142/1324/1342/2431/2341/....

J'ai pu générer tous les permutations possibles mais pas ceux admissibles.
 
  static void permute(ArrayList<Integer> arr, int k){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            System.out.println(java.util.Arrays.toString(arr.toArray()));
        }
 
    }


J'ai vraiment besoin de ce code pour calculer la valeur de Owen (théorie des jeux). Merci en avance
A voir également:

2 réponses

Messages postés
14790
Date d'inscription
vendredi 14 mars 2003
Statut
Modérateur
Dernière intervention
15 mai 2021
155
Pour pouvoir t'aider, il faut connaitre la condition qui fait qu'une permutation est autorisée ou pas.
Messages postés
57
Date d'inscription
dimanche 6 décembre 2009
Statut
Membre
Dernière intervention
17 mars 2015

Salut,
Les permutations autorisé sont des combinaisons des permutations des sous ensembles. Dans cet exemple:List = {(1,2),(3,4)} , l'ensemble list est composé de deux sous ensemble: {1,2} et l'ensemble {3,4}. Il faut combiner les permuations de ces deux ensembles. Par exemple: la permutation 1342 n'est pas autorisé,puisque après le on doit avoir le 2 qui appartient au même ensemble que 1.
Messages postés
14790
Date d'inscription
vendredi 14 mars 2003
Statut
Modérateur
Dernière intervention
15 mai 2021
155
As-tu essayé de faire une fonction qui contrôle cela ?