Générer tous les permutations admissibles

Question

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

NHenry · Answer

Pour pouvoir t'aider, il faut connaitre la condition qui fait qu'une permutation est autorisée ou pas.

ImFaith · Answer

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.

Générer tous les permutations admissibles

2 réponses

Votre réponse

Discussions similaires