How to Generate All Unique Permutations of an Array, Including Handling Repeated Elements?

Permutation of array

Permutations of an array are all the possible ways of arranging the elements of the array in a different order. For example, the array [1, 2, 3] has the following permutations:

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

There are several algorithms to generate permutations of an array. One of the most common algorithms is a recursive algorithm that generates all permutations of a smaller array by adding the new element to the end of each permutation of the smaller array.

Here is an implementation of the recursive algorithm in 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));
        }
    }
}

The code above prints all the permutations of the array a to the console.

Handling repeated elements

The recursive algorithm above does not handle repeated elements correctly. For example, if the array a contains repeated elements, then the algorithm will generate duplicate permutations.

To handle repeated elements, we can use a different algorithm called the Heap's algorithm. Heap's algorithm generates all permutations of an array by iteratively swapping two elements of the array.

Here is an implementation of Heap's algorithm in 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);
                }
            }
        }
    }
}

The code above prints all the unique permutations of the array a to the console.

The above is the detailed content of How to Generate All Unique Permutations of an Array, Including Handling Repeated Elements?. For more information, please follow other related articles on the PHP Chinese website!