0

我在编写返回 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);

      }
  }
}

这对字符串很有用，但是当我尝试为 ArrayLists 重写它时 - 我发现了一些麻烦。

这是我写的代码：

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 个小时，但我仍然遇到其他问题......

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

提前致谢。

4

2 回答 2

1

也许你的错误在那里：

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

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

于 2013-01-15T22:53:51.387 回答
0

您要查找的内容称为Backtracking。这种解决问题的技术很大程度上基于递归。基本上，你设置你的第一个点，然后只考虑其他点作为一个子问题，当找到第一个点的每个排列时，它就会增加，依此类推。

您的解决方案将类似于以下内容。为简单起见，我使用整数数组制作它，但您应该能够轻松地将整数更改为点。将这些整数视为 Arraylist 中点的索引。

public class PermutationDemo {

    public static void main(String[] args) {
        int[] array = new int[4];

        for (int i=0; i<array.length; i++) {
            reset(array, i);
        }

        solve(array, 0);
    }

    private static void solve(int[] array, int i) {
        if (i == array.length) {
            print(array);
            return;
        }

        for (int k=0; k<4; k++) {
            solve(array, i+1);
            makeMove(array, i);
        }

        reset(array, i);
    }

    private static void makeMove(int[] array, int i) {
        array[i] += 1;
    }

    private static void reset(int[] array, int i) {
        array[i] = 1;
    }

    private static void print(int[] array) {
        for (int i=0; i<array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println("");
    }
}

结果是：

PS [10:21] Desktop > java PermutationDemo
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
1 2 2
1 2 3
1 2 4
1 3 1
1 3 2
1 3 3
1 3 4
1 4 1
1 4 2
1 4 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4
2 2 1
2 2 2
2 2 3
2 2 4
2 3 1
2 3 2
2 3 3
2 3 4
2 4 1
2 4 2
2 4 3
2 4 4
3 1 1
3 1 2
3 1 3
3 1 4
3 2 1
3 2 2
3 2 3
3 2 4
3 3 1
3 3 2
3 3 3
3 3 4
3 4 1
3 4 2
3 4 3
3 4 4
4 1 1
4 1 2
4 1 3
4 1 4
4 2 1
4 2 2
4 2 3
4 2 4
4 3 1
4 3 2
4 3 3
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4
于 2013-10-29T09:28:51.310 回答