Java fonction pour calculer permutations sans répétitions

J'ai un ArrayList et je veux trouver toutes les combinaisons d'une taille donnée sans répétitions à l'intérieur avec une seule fonction (intégré ou non). Par exemple:Java fonction pour calculer permutations sans répétitions

ArrayList<Integer> numbers = Array.asList(96, 32, 65, 21); 
getCombinationsWithoutRepeats(numbers, 2);

Sortie:

>>> [[96, 32], [96, 65], [96, 21], [32, 65], [32, 21], [65, 21]]

Comment puis-je créer cette fonction ou est-il une fonction intégrée qui fait cela?

Source

2013-06-23 LazySloth13

En relation: [permutation de tableau] (http://stackoverflow.com/a/2920349/335858). – dasblinkenlight

Pouvons-nous supposer que le tableau d'entrée a seulement des éléments uniques (je suppose par "répétitions" que vous voulez dire dans la sortie)? Une solution très évidente consiste à générer d'abord toutes les combinaisons de taille 'n' (la façon la plus courante de le faire est de représenter l'ensemble avec un nombre' n'-bit que vous incrémentez à plusieurs reprises.À chaque fois, la représentation binaire du nombre vous dit quels éléments inclure/exclure dans/de la combinaison actuelle) puis permuter chacune des combinaisons (par exemple, la solution lexicographique populaire: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order). – rliu

Qu'avez-vous essayé? – Ayman

-1

Voici une solution d'exemple, en utilisant le retour arrière. Il va générer toutes les permutations possibles de taille K et les stocker dans le champ lists.

List<List<Integer>> lists = new ArrayList<List<Integer>>(); 

void permutate(int[] arr, int k) { 
    internalPermutate(arr, k, 0, 0); 
} 

void internalPermutate(int[] arr, int k, int step, int index) { 
    if (step == k) { 
     List<Integer> list = new ArrayList<Integer>(); 
     for (int i = 0; i < k; i++) { 
      list.add(arr[i]); 
     } 
     lists.add(list); 
    } 

    for (int i = step + index; i < arr.length; i++) { 
     swap(arr, step, i); 
     internalPermutate(arr, k, step + 1, i); 
     swap(arr, step, i); 
    } 
} 

private void swap(int[] arr, int x, int y) { 
    int temp = arr[x]; 
    arr[x] = arr[y]; 
    arr[y] = temp; 
} 

public static void main(String[] args) { 
    new SomeClass().permutate(new int[] { 1, 2, 3, 4 }, 2); 
    System.out.println(lists); 
}

Cette solution ne traite pas de la situation quand nous avons les mêmes éléments dans le tableau, mais vous pouvez les exclure avant tout permutation.

Source

2013-06-23 11:04:58 Desert

Cela ne fonctionne pas pour tout ce qui dépasse la taille k = 1 – CODe

Java fonction pour calculer permutations sans répétitions

Répondre

Questions connexes