列表列表中的堆算法实现 [英] Heap's Algorithm implementation in list of lists

问题描述

我正在使用堆的算法来创建一个列表列表，其中包含所述列表的每个排列.每个排列都是它自己的列表.当我在算法中打印它时它可以正常工作，但是当我尝试将它添加到我的列表列表时它不能正常工作并且它们都是相同的数组(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. 您对相同的对象进行另一个排列.
4. 您将对象添加到 ArrayList 中，该对象已经在此列表中.

最后你有 20 次添加相同 int 数组的 ArrayList.

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

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