置换算法，用于创建所有排列的数组-Java 学习之路

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

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

有人能告诉我，如果我正在考虑这个问题，他们是否有任何想法或提示要给我？我没有代码可以分享，因为我一直白人寄宿我的大部分想法 .

2 回答

如果我理解正确，这是你想要的吗？

public class MyClass_3928{

    static List<String> listOfAllArrays = new ArrayList<>();

    public static void calculate(int[] list, int n) {
        if (n == 1) {
            listOfAllArrays.add(Arrays.toString(list));
        } else {
            for (int i = 0; i < n; i++) {
                calculate(list, n - 1);

                int j = (n % 2 == 0) ? i : 0;

                int t = list[n - 1];
                list[n - 1] = list[j];
                list[j] = t;
            }
        }

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("How many numbers would you like to permute?");
        int numbers = Integer.valueOf(scanner.nextLine());
        int[] numbersArray = new int[numbers-1];
        System.out.println("Those numbers are");
        for (int i = 0; i < numbers-1; i++) {
            numbersArray[i] = i+1;
        }

        calculate(numbersArray, numbersArray.length);

        for (int i = 0; i < listOfAllArrays.size(); i++) {
            System.out.println(listOfAllArrays.get(i));
        }

    }

回复于 2024-05-02T06:41:46+08:00

1
置换可以在典型的 Backtrack 算法中解决，我们必须使用 traverse all possibilities in the state space . Backtrack是一个非常重要的算法，我的建议是你看一下它（通常是递归形式）并试图掌握它的基本思想，而不是试图以你自己的方式解决permuation问题 .

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

You can compare backtrack with DFS, or traveral algorithm on a binary tree. They are in many places very similar with each other.

下面是我对这个问题的解决方案，其结果是一个arrayList和permutaion是根据 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);
    }

}
```
}
回复于 2024-05-02T06:41:46+08:00

置换算法，用于创建所有排列的数组

2 回答

相关问题