1

我的代码的目标：尝试创建一个数组的 ArrayList，其中包含传递的数组“p”的所有排列。

方法：使用Heap 的算法，尝试生成所有排列，每个排列 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 个这样的排列。）

如果我删除了数组列表，并且只是简单地使用打印来获取排列，则排列都是由这段代码正确生成的......

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

问题/查询：

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

1 回答 1

3

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

您想要做的是将包含的数据p添加到您的数组列表中。您可以简单地执行此添加p.clone()而不是p（有关此机制的更多详细信息，请参见Java 数组的 Clone 方法）。

然后，当您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
于 2020-02-21T19:46:45.303 回答