Comment pouvons-nous générer toutes les permutations possibles d'un tableau, en gérant à la fois des éléments distincts et non distincts ?

Permutation d'un tableau

Générer des permutations d'un tableau est une tâche informatique courante. Étant donné un tableau d'éléments distincts, comment pouvons-nous calculer tous les arrangements possibles de ces éléments ?

Algorithme récursif

Un algorithme classique de génération de permutation utilise la récursion. L'idée principale est de considérer chaque élément du tableau comme un premier élément potentiel, puis de permuter récursivement les éléments restants pour trouver toutes les combinaisons possibles en commençant par ce premier élément :

// Recursive method for permutation generation
public static void permute(int[] arr, int k) {
    for (int i = k; i < arr.length; i++) {
        // Swap elements at positions k and i
        Collections.swap(arr, k, i);
        // Recursively permute the remaining elements
        permute(arr, k + 1);
        // Restore original order of elements
        Collections.swap(arr, k, i);
    }
    if (k == arr.length - 1) {
        // Once all elements are permuted, print the current permutation
        System.out.println(Arrays.toString(arr));
    }
}

Dans cet algorithme, le paramètre k garde une trace de la position actuelle dans le tableau. Initialement, k est mis à 0, indiquant le premier élément. Pour chaque position k, il parcourt les éléments restants, en les échangeant avec l'élément à la position k et en permutant récursivement le reste du tableau en commençant par la position k 1. Cela considère efficacement tous les arrangements possibles en commençant par chaque élément.

Algorithme non récursif pour éléments distincts

Un algorithme alternatif non récursif fonctionne bien pour les cas où tous les éléments du tableau sont distincts. Il crée des permutations en échangeant de manière itérative des éléments pour obtenir un modèle spécifique :

for (int tail = arr.length - 1; tail > 0; tail--) {
    // Find the first decreasing element from the end
    if (arr[tail - 1] < arr[tail]) {
        // Find the last element greater than the decreasing element
        int s = arr.length - 1;
        while (arr[tail - 1] >= arr[s]) {
            s--;
        }
        // Swap the decreasing element with the greater element
        swap(arr, tail - 1, s);
        // Reverse the order of elements after the swap
        reverse(arr, tail);
        break;
    }
}

Cet algorithme commence par une séquence ascendante d'éléments dans le tableau. Il parcourt le tableau de droite à gauche, à la recherche du premier élément décroissant. Une fois qu'il a trouvé l'élément décroissant, il l'échange avec le plus petit élément de la queue du tableau qui lui est supérieur. Enfin, il inverse l'ordre des éléments dans la queue pour obtenir la permutation suivante.

Algorithme non récursif pour les mêmes éléments

Dans les cas où les éléments du tableau ne sont pas distincts, l'utilisation de HashMap pour mapper les éléments à leurs indices peut gérer des répétitions potentielles :

// Create a HashMap to map elements to their indices
Map<E, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    map.put(arr[i], i);
}
// Sort the array in ascending order
Arrays.sort(arr);
// Initialize the index array
int[] ind = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    ind[i] = map.get(arr[i]);
}

Avec un mappage approprié et indexation, le même algorithme non récursif peut générer toutes les permutations, en gérant les éléments répétés de manière appropriée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!