列表列表中的堆算法实现

问题描述

我正在使用Heap的算法来创建一个列表列表，其中包含所述列表的每个排列.每个排列将是其自己的列表.当我在算法中打印它时，它可以正常工作，但是当我尝试将其添加到列表中并且它们都是相同的数组(4、1、2、3)时，它却无法正常工作.我注释掉了我测试过的打印件，以确保它可以正常工作.

I'm using Heap's algorithm to create a list-of-lists containing each permutation of said list. Each permutation will be its own list. It works properly when I print it within the algorithm, but it doesn't work properly when I try to add it to my list-of-lists and they are all the same array (4, 1, 2, 3). I commented out the print that I tested to make sure it was working.

我当前的代码:

public static ArrayList<int[]> lists = new ArrayList<>();

public static void main(String[] args) {
    int[] list = {1,2,3,4};
    heapsAlgorithm(4,list);
    for(int i = 1; i <= lists.size(); i++) {
        System.out.println("List " + i + ": " + Arrays.toString(lists.get(i-1)));
    }
}

public static void heapsAlgorithm(int n, int[] list) {
    if (n == 1) {
        lists.add(list);
        //System.out.println(Arrays.toString(list));
    }
    else {
        for(int i = 0; i < n; i++) {
            heapsAlgorithm(n - 1, list);
            if ( n % 2 == 0) {
                int swap = list[i];
                list[i] = list[n-1];
                list[n-1] = swap;
            }
            else {
                int swap = list[0];
                list[0] = list[n-1];
                list[n-1] = swap;
            }
        }
    }
}

工作:

[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[4, 2, 3, 1]
[2, 4, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
[2, 3, 4, 1]
[3, 2, 4, 1]
[4, 1, 3, 2]
[1, 4, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[1, 3, 4, 2]
[3, 1, 4, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 2, 4, 3]
[2, 1, 4, 3]

错误的输出:

List 1: [4, 1, 2, 3]
List 2: [4, 1, 2, 3]
List 3: [4, 1, 2, 3]
List 4: [4, 1, 2, 3]
List 5: [4, 1, 2, 3]
List 6: [4, 1, 2, 3]
List 7: [4, 1, 2, 3]
List 8: [4, 1, 2, 3]
List 9: [4, 1, 2, 3]
List 10: [4, 1, 2, 3]
List 11: [4, 1, 2, 3]
List 12: [4, 1, 2, 3]
List 13: [4, 1, 2, 3]
List 14: [4, 1, 2, 3]
List 15: [4, 1, 2, 3]
List 16: [4, 1, 2, 3]
List 17: [4, 1, 2, 3]
List 18: [4, 1, 2, 3]
List 19: [4, 1, 2, 3]
List 20: [4, 1, 2, 3]
List 21: [4, 1, 2, 3]
List 22: [4, 1, 2, 3]
List 23: [4, 1, 2, 3]
List 24: [4, 1, 2, 3]

我认为我在错误地使用ArrayList，但是我不确定在哪里.有什么建议吗?

I assume I am using my ArrayList wrong, but I'm not sure where. Any suggestions?

推荐答案

您需要复制int数组.

You are need to copy your int array.

您有一个可变的数组实例，并假定要保留排列的数组列表.基本上，发生了什么:

You have an mutable instance of your array and list of arrays that you assume you to keep your permutations. Basically, what's happening:

1. 您可以进行排列.
2. 您将排列添加到ArrayList中.
3. 您在THE SAME对象上进行另一个置换.
4. 将对象添加到已经在此列表中的ArrayList中.

最后，您有20次ArrayList添加了相同的int数组.

At the end you have ArrayList with 20 times added the same int array.

这篇关于列表列表中的堆算法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！