如何生成数组的所有排列，包括具有重复值的情况？

数组的排列

给定一个不同整数的数组，找到总数并列出该数组所有可能的排列。

代码

以下代码提供了一个递归算法来查找数组的排列：

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;
    }
}

该算法通过将第一个元素与数组中的每个其他元素交换来生成数组的所有排列，然后递归调用剩余数组上的算法。

迭代器和重复情况的扩展value

该算法的缺点是它不处理数组中重复值的情况。为了处理这种情况，我们可以修改算法以使用堆栈而不是递归。以下代码提供了用于查找数组排列的迭代算法：

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;
    }
}

此算法使用堆栈来跟踪当前排列。该算法首先将数组的第一个元素压入堆栈。然后，该算法重复从堆栈中弹出元素，并将它们与数组中下一个未访问的元素交换。如果数组中不再有未访问的元素，算法会从堆栈中弹出该元素，并继续处理堆栈中的下一个元素。

以上是如何生成数组的所有排列，包括具有重复值的情况？的详细内容。更多信息请关注PHP中文网其他相关文章！