代码之家 › 专栏 › 技术社区 › A.Torres

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

permutation algorithm java

A.Torres · 技术社区 · 6 年前

我正在尝试写一个称为排列的方法。基本上,我希望它接受一个整数,然后返回从0到x-1的所有数字排列。我知道这应该返回一个数组数组。然而,我在努力实现这一点。有人能帮我更好地考虑这个问题吗?我用Java编码。我意识到这可能是一个递归问题,但除此之外,我处于一个损失中。

我考虑过有两种方法,一种是接收整数并从0-x-1生成第一个数组。然后是另一个接受数组和整数“start”的方法。这样索引开始处的整数就不会改变,但会与其他数字交换。这将在for循环的内部,这样“start”位置将在整个数组中更改。唯一的提示是for循环将递归调用该方法。但是,我很难思考如何实际实现这一点以及交换的算法。

有人能告诉我我是否在考虑这个权利,他们是否有什么想法或提示要给我?我没有可以分享的代码,因为我已经白手起家了,对此我的大部分想法。

2 回复 | 直到 6 年前

ZhaoGang 6 年前

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

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

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

下面是我对这个问题的解决方案,在这个问题中,结果是一个数组列表,排列是根据 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);
    }

}

}

MS90 6 年前

如果我正确理解你,这是你想要的吗?

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

    }