java - 查找 ArrayList 的所有排列并将它们放入新的 ArrayList>

Question

我在编写返回 ArrayList 的所有排列的方法代码时遇到一些问题。

我找到了该算法:

public class MainClass {
  public static void main(String args[]) {
    permuteString("", "String");
  }

  public static void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1)
      System.out.println(beginningString + endingString);
    else
      for (int i = 0; i < endingString.length(); i++) {
          String newString = endingString.substring(0, i) + endingString.substring(i + 1);
          permuteString(beginningString + endingString.charAt(i), newString);

      }
  }
}

这对于字符串来说非常有用，但是当我尝试为 ArrayList 重写它时 - 我发现了一些麻烦。

这是我编写的代码:

private static ArrayList<ArrayList<Point>> listaPermutacji = new ArrayList<ArrayList<Point>>();

public static void perm(ArrayList<Point> soFar, ArrayList<Point> rest) {
        if (rest.size() <= 1) {
            ArrayList<Point> temp = new ArrayList<Point>();
            temp = soFar;
            for (int i = 0; i < rest.size(); i++) {
                temp.add(rest.get(i));
            }
            listaPermutacji.add(temp);
        } else {
            for (int k = 0; k < rest.size(); k++) {
                ArrayList<Point> remaining = new ArrayList<Point>();
                List<Point> sublist = rest.subList(0, k);
                for (int a = 0; a < sublist.size(); a++) {
                    remaining.add(sublist.get(a));
                }
                sublist.clear();
                if (rest.size() >= k + 1) {
                    sublist = rest.subList(k + 1, rest.size());
                    for (int a = 0; a < sublist.size(); a++) {
                        remaining.add(sublist.get(a));
                    }
                }
                ArrayList<Point> beginning = new ArrayList<Point>();
                beginning = soFar;
                System.out.println("Beginning size= " + beginning.size());
                System.out.println("Rest size= " + rest.size());
                System.out.println("k= " + k);
                if(k<rest.size()){
                    beginning.add(rest.get(k));
                }
                perm(beginning, remaining);
            } 
        } 
    }

这是返回的，例如 3 点数组:

x= 4.0 y= 3.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 4.0 y= 3.0 | 
x= 4.0 y= 3.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 4.0 y= 3.0 | 
x= 4.0 y= 3.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 1.0 y= 0.0 | x= 0.0 y= 1.0 | x= 4.0 y= 3.0 | 

我真的无法理解...我尝试修复这个问题大约 4 个小时，但我仍然遇到其他问题...

顺便说一句，我需要这个生成器来解决旅行商问题的暴力方法...

提前致谢。

Answer 1

也许你的错误就在那里:

 ArrayList<Point> temp = new ArrayList<Point>();
 temp = soFar;

如果你想要temp要成为副本(新列表)，您应该将这两行替换为 ArrayList<Point> temp = new ArrayList<Point>(soFar);