Comment générer toutes les permutations uniques d'un tableau, y compris la gestion des éléments répétés ?

Permutation d'un tableau

Les permutations d'un tableau sont toutes les manières possibles d'organiser les éléments du tableau dans un ordre différent. Par exemple, le tableau [1, 2, 3] a les permutations suivantes :

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

Il existe plusieurs algorithmes pour générer des permutations d'un tableau. L'un des algorithmes les plus courants est un algorithme récursif qui génère toutes les permutations d'un tableau plus petit en ajoutant le nouvel élément à la fin de chaque permutation du plus petit tableau.

Voici une implémentation de l'algorithme récursif en Java :

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        for (int i = k; i < a.length; i++) {
            java.util.Collections.swap(a, i, k);
            permute(a, k + 1);
            java.util.Collections.swap(a, i, k);
        }
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        }
    }
}

Le code ci-dessus imprime toutes les permutations du tableau a au console.

Gestion des éléments répétés

L'algorithme récursif ci-dessus ne gère pas correctement les éléments répétés. Par exemple, si le tableau a contient des éléments répétés, alors l'algorithme générera des permutations en double.

Pour gérer les éléments répétés, nous pouvons utiliser un algorithme différent appelé algorithme du tas. L'algorithme de Heap génère toutes les permutations d'un tableau en échangeant de manière itérative deux éléments du tableau.

Voici une implémentation de l'algorithme de Heap en Java :

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 3, 4, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        } else {
            for (int i = k; i < a.length; i++) {
                if (i == k || a[i] != a[k]) {
                    java.util.Collections.swap(a, i, k);
                    permute(a, k + 1);
                    java.util.Collections.swap(a, i, k);
                }
            }
        }
    }
}

Le code ci-dessus imprime toutes les permutations uniques du tableau a à la console.

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!