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は、これらの2行を次のように置き換える必要があります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 に答える