How to Generate All Permutations of an Array, Including Cases with Repeated Values?

Permutation of array

Given an array of distinct integers, find the total number and list all possible permutations of the array.

Code

The following code provides a recursive algorithm for finding the permutations of an array:

import java.util.*;

public class Permute {

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

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

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

This algorithm generates all the permutations of the array by swapping the first element with each of the other elements in the array, and then recursively calling the algorithm on the remaining array.

Iterators and Extension to the case of repeated values

The drawback of this algorithm is that it does not handle the case of repeated values in the array. To handle this case, we can modify the algorithm to use a stack instead of recursion. The following code provides an iterative algorithm for finding the permutations of an array:

import java.util.*;

public class Permute {

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

    private static void permuteIterative(int[] a) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        stack.push(0);
        visited.add(0);

        while (!stack.isEmpty()) {
            int k = stack.peek();
            if (k == a.length - 1) {
                System.out.println(Arrays.toString(a));
                stack.pop();
            } else {
                for (int i = k + 1; i < a.length; i++) {
                    if (!visited.contains(i)) {
                        swap(a, i, k);
                        stack.push(i);
                        visited.add(i);
                        break;
                    }
                }
                if (stack.peek() == k) {
                    stack.pop();
                    visited.remove(k);
                }
            }
        }
    }

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

This algorithm uses a stack to keep track of the current permutation. The algorithm starts by pushing the first element of the array onto the stack. Then, the algorithm repeatedly pops elements from the stack and swaps them with the next unvisited element in the array. If there are no more unvisited elements in the array, the algorithm pops the element from the stack and continues with the next element in the stack.

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