Permutations d'un tableau en Java

1. Introduction

Dans cet article, nous verrons comment créer des permutations d'un tableau.

Tout d'abord, nous allons définir ce qu'est une permutation. Deuxièmement, nous examinerons certaines contraintes. Et troisièmement, nous examinerons trois façons de les calculer: de manière récursive, itérative et aléatoire.

Nous nous concentrerons sur l'implémentation en Java et n'entrerons donc pas dans beaucoup de détails mathématiques.

2. Qu'est-ce qu'une permutation?

Une permutation d'un ensemble est un réarrangement de ses éléments. Un ensemble composé de n éléments a n! permutations. Ici n! est la factorielle, qui est le produit de tous les entiers positifs inférieurs ou égaux à n .

2.1. Exemple

Le tableau d'entiers [3,4,7] comporte trois éléments et six permutations:

n! = 3! = 1 x 2 x 3 = 6

Permutations: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Contraintes

Le nombre de permutation augmente rapidement avec n . Bien que cela ne prenne que quelques secondes pour générer toutes les permutations de dix éléments, il faudra deux semaines pour générer toutes les permutations de 15 éléments:

3. Algorithmes

3.1. Algorithme récursif

Le premier algorithme que nous examinons est l'algorithme de Heap. C'est un algorithme récursif qui produit toutes les permutations en échangeant un élément par itération.

Le tableau d'entrée sera modifié. Si nous ne voulons pas cela, nous devons créer une copie du tableau avant d'appeler la méthode:

public static  void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } else { for(int i = 0; i < n-1; i++) { printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) { swap(elements, i, n-1); } else { swap(elements, 0, n-1); } } printAllRecursive(n - 1, elements, delimiter); } } 

La méthode utilise deux méthodes d'assistance:

private void swap(T[] input, int a, int b) { T tmp = input[a]; input[a] = input[b]; input[b] = tmp; }
private void printArray(T[] input) { System.out.print('\n'); for(int i = 0; i < input.length; i++) { System.out.print(input[i]); } } 

Ici, nous écrivons le résultat dans System.out , cependant, nous pouvons facilement stocker le résultat dans un tableau ou dans une liste à la place.

3.2. Algorithme itératif

L'algorithme de Heap peut également être implémenté à l'aide d'itérations:

int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 

3.3. Permutations dans l'ordre lexicographique

Si les éléments sont comparables, nous pouvons générer des permutations triées par ordre naturel des éléments:

public static 
    
      void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i > 0; i--) { if (elements[i].compareTo(elements[i - 1]) > 0) { k = i - 1; hasNext = true; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } } 
    

Cet algorithme a une opération inverse à chaque itération et est donc moins efficace sur les tableaux que l'algorithme de Heap.

3.4. Algorithme aléatoire

Si n est grand, nous pouvons générer une permutation aléatoire en mélangeant le tableau:

Collections.shuffle(Arrays.asList(elements));

Nous pouvons le faire plusieurs fois pour générer un échantillon de permutations.

Nous pourrions créer les mêmes permutations plus d'une fois, cependant, pour de grandes valeurs de n , les chances de générer la même permutation deux fois sont faibles.

4. Conclusion

Il existe de nombreuses façons de générer toutes les permutations d'un tableau. Dans cet article, nous avons vu l'algorithme de Heap récursif et itératif et comment générer une liste triée de permutations.

Il n'est pas possible de générer toutes les permutations pour les grands tableaux, par conséquent, nous pouvons générer des permutations aléatoires à la place.

L'implémentation de tous les extraits de code de cet article se trouve dans notre référentiel Github.