使用堆算法生成排列时出错

Question

Objective 我的代码： 尝试创建一个包含传递数组 'p'.

所有排列的数组的 ArrayList

方法：使用Heap's algorithm，尝试生成所有排列，每个排列bieng存储在ArrayList中，使用add()方法。

问题代码进入： ArrayList 中的所有元素都更新为相同的值（找到的最新排列的值）。

代码：

import java.io.IOException;
import java.util.ArrayList;

class Main
{
   static ArrayList<int[]> arrayList=new ArrayList<>();

    static void getCombo(int[] p, int size, int n){

        if(size==1){
            arrayList.add(p);
            System.out.println("added new permutation");
            for(int i=0;i<arrayList.size();++i){
                for(int j:arrayList.get(i)) {
                    System.out.print(j);}
                System.out.println("");
                }
        }

        for (int i=0; i<size; i++)
        {
            getCombo(p,size-1, n);
            // if size is odd, swap first and last
            if ((size&1)!=0) p[0]=p[0]^p[size-1]^(p[size-1]=p[0]) ;
                // If size is even, swap ith and last
            else p[i]=p[i]^p[size-1]^(p[size-1]=p[i]) ;
        }
    }


    public static void main(String args[]) throws IOException {
        int[] arr={1,2,3} ;
        getCombo(arr, arr.length,arr.length);
    }

}

O/P 代码：

added new permutation
123
added new permutation
213
213
added new permutation
312
312
312
added new permutation
132
132
132
132
added new permutation
231
231
231
231
231
added new permutation
321
321
321
321
321
321

期望O/P：列表应包含在每次迭代中添加的不同排列。（在这种情况下，存在 6 个这样的排列。）

如果我删除 ARRAYLIST，并且只是简单地使用 print 来获取排列，则所有排列均由此代码正确生成...

import java.io.IOException;
import java.util.ArrayList;

class Main
{
   static ArrayList<int[]> arrayList=new ArrayList<>();

    static void getCombo(int[] p, int size, int n){

        if(size==1){
            for(int i:p) System.out.print(i);
            System.out.println();
        }

        for (int i=0; i<size; i++)
        {
            getCombo(p,size-1, n);
            // if size is odd, swap first and last
            if ((size&1)!=0) p[0]=p[0]^p[size-1]^(p[size-1]=p[0]) ;
                // If size is even, swap ith and last
            else p[i]=p[i]^p[size-1]^(p[size-1]=p[i]) ;
        }
    }


    public static void main(String args[]) throws IOException {
        int[] arr={1,2,3} ;
        getCombo(arr, arr.length,arr.length);
    }

    }

O/P:
123
213
312
132
231
321

Question/Query:

请告诉为什么会这样，好像我选择在每个 if(size==1) 条件下直接打印数组 'p'，那么 o/p 是正确的，只有 ArrayList 实现是创建问题...
有什么解决办法？（最好是最有效的修复）。

Answer 1

正如@Scratte 所指出的，您只会将一个数组 (p) 添加到您的列表中。您向它添加了多个引用，但它在幕后始终是同一个数组，因此如果您修改该数组，您每次打印时都会看到相同的数据。

您要做的是将 p 中包含的 data 添加到数组列表中。您可以简单地添加 p.clone() 而不是 p（有关此机制的更多详细信息，请参阅 Clone method for Java arrays）。

然后当您在程序中进一步更改 p 时，您不会同时修改存储的数据。

如果我更改您的代码

static void getCombo(int[] p, int size, int n) {
    if (size == 1) {
        arrayList.add(p);
        ...

到

static void getCombo(int[] p, int size, int n) {
    if (size == 1) {
        arrayList.add(p.clone());
        ...

我得到这个输出：

added new permutation
123
added new permutation
123
213
added new permutation
123
213
312
added new permutation
123
213
312
132
added new permutation
123
213
312
132
231
added new permutation
123
213
312
132
231
321

使用堆算法生成排列时出错

Error generating permutations using Heap's Algorithm

java

heaps-algorithm