Comment puis-je générer toutes les permutations d'un tableau à l'aide d'algorithmes récursifs et non récursifs ?

Permutation d'un tableau : une explication approfondie

Pour générer des permutations d'un tableau, il est crucial de comprendre comment les éléments sont disposés. Une permutation implique de réorganiser les éléments du tableau pour créer de nouvelles séquences. Le nombre de permutations possibles pour un tableau avec n éléments est donné par n !.

Algorithme récursif

Une façon de générer des permutations consiste à utiliser une approche récursive, où vous échangez itérativement les éléments et appliquez des permutations sur les éléments restants du tableau.

public static void permute(java.util.List<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()));
    }
}

Cet algorithme commence par échanger le premier élément avec chacun des éléments restants. Ensuite, il applique récursivement la même opération sur les éléments restants. Après chaque appel récursif, les éléments sont replacés dans leurs positions d'origine.

Algorithme non récursif

Pour une approche itérative, considérez les étapes suivantes :

1. Commencez par le tableau trié par ordre croissant.
2. Trouvez le premier index où la séquence ne parvient pas à être décroissante (c'est-à-dire où a[i] < a[i-1]).
3. Trouvez le dernier index où la valeur est supérieure ou égale à a[i-1].
4. Échangez a[i-1] avec l'élément au dernier index.
5. Inversez l'ordre des éléments dans la queue du tableau (après l'index i-1).

Exemple : Permutation d'un tableau [3, 4, 6, 2, 1]

Algorithme récursif :

1. Échangez 3 avec 4 : [4, 3, 6, 2, 1]
2. Permuter récursivement [4, 3, 6, 2, 1]
3. Échanger 3 avec 6 : [4, 6, 3, 2, 1]
4. Permuter récursivement [4, 6, 3, 2, 1]
5. Continuez jusqu'à ce que toutes les permutations soient générées

Algorithme non récursif :

1. Commencez par [1, 2, 3, 4, 6] (triés par ordre croissant)
2. La séquence est décroissant, passez donc à l'étape 3
3. Trouvez le premier index où a[i] < a[i-1] : i = 4, puisque 3 &Lt ; 4
4. Trouver le dernier index où a[j] >= a[i-1] : j = 5, puisque 6 >= 3
5. Echanger a[i-1] avec a[j] : [1, 2, 6, 3, 4, 5]
6. Inverser la queue du tableau : [1, 2, 3, 4, 5, 6]
7. Répétez les étapes 3 à 6 jusqu'à ce que le tableau soit dans l'ordre décroissant (indiquant que toutes les permutations ont été générées)

Le résultat pour les deux algorithmes c'est pareil : toutes les permutations possibles sont générées et imprimées.

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!