java - 创建所有排列数组的排列算法

Question

我正在尝试编写一种称为排列的方法。基本上，我希望它接受一个整数，然后返回从 0 到 x -1 的所有数字排列。我意识到这应该返回一个数组数组。但是，我正在努力实际执行此操作。有人可以帮我更好地思考这个问题吗？我正在用 java 编写代码。我意识到这可能是一个递归问题，但除此之外我不知所措。

我想过有两种方法，一种接受整数并从 0 - x-1 生成第一个数组。然后是另一种方法，它接受一个数组和一些整数“开始”。这样索引开始的整数不会改变，但会与其他数字交换。这将在 for 循环内，以便“开始”位置将在整个数组中发生变化。我得到的唯一提示是我的 for 循环将递归调用该方法。但是，我在考虑如何实际实现它和交换算法时遇到了麻烦。

有人可以告诉我我是否正在考虑这个权利，以及他们是否有任何想法或提示可以给我？我没有代码可以分享，因为我已经将我的大部分想法白板化了。

Answer 1

排列可以在典型的回溯算法中解决，在该算法中我们必须遍历状态空间中的所有可能性。回溯是一个非常重要的算法，我的建议是你看一下它(通常是递归形式)并尝试掌握它的基本思想，而不是试图用你自己的方式解决置换问题。

基本上要找到一个排列，我们必须走 n 步(设置一位是一步)，在我们为每一步选择一位之后，我们有一个排列，所以我们有一个可能的解决方案(比如，它是 1,2,3,4,5,6)。之后，我们回溯到倒数第二位，注意我们在第一个解决方案中选择了5，但是我们可以有另一个选择6，之后我们只有一个选择最后一位是 5。对于其他解决方案，我们继续回溯到倒数第三位、倒数第四位……等等。这就是回溯命名的原因。

您可以将回溯与 DFS 或二叉树上的遍历算法进行比较。它们在很多地方彼此非常相似。

下面是我对这个问题的解决方案，其中结果是一个 arrayList 并且排列是根据 1...n 而不是 0...n-1，但里面的思想是一模一样的。

class Solution {
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> permutations=new ArrayList();
    backtrack(permutations,new ArrayList<Integer>(),nums);
    return permutations;
}

private void backtrack(List<List<Integer>> permutations,List<Integer> tempList,int[] nums){
    if(tempList.size()==nums.length){
        permutations.add(new ArrayList<Integer>(tempList));
        return;
    }

    for(int i=0;i<nums.length;i++){
        if(tempList.contains(nums[i])){
            continue;
        }

        tempList.add(nums[i]);    
        backtrack(permutations,tempList,nums);
        tempList.remove(tempList.size()-1);
    }

}