16

リスト内のすべてのアイテムを再帰的に再帰的に生成しようとしています。これと同様の質問に対するいくつかの解決策を見てきましたが、コードを機能させることができませんでした。誰かが私のコードを修正する方法を指摘できますか?

これは、Java 関係者だけでなく、すべての S/O'er に開かれています。

（また、SO例外でクラッシュすることに注意してください）。

サンプル入力:

[1, 2, 3]

出力：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

//allPossibleItems is an AL of all items 

//this is called with generatePerm(null, new ArrayList<Item>);

private void generatePerm(Item i, ArrayList<Item> a) {
    if (i != null) { a.add(i); }
    if (a.size() == DESIRED_SIZE) {
        permutations.add(a);
        return;
    }
    for (int j = 0; j < allPossibleItems.size(); j++) {
        if (allPossibleItems.get(j) != i)
            generatePerm(allPossibleItems.get(j), a);
    }
}
4

6 に答える 6

24

が 2 つの異なる要素 x と y を含む場合allPossibleItems、 x と y を に達するまで連続してリストに書き込みますDESIRED_SIZE。それはあなたが本当に欲しいものですか？十分な大きさを選択DESIRED_SIZEすると、スタックに再帰呼び出しが多すぎるため、SO 例外が発生します。

私がすること（オリジナルにダプレット/重複がない場合）は次のとおりです。

public <E> List<List<E>> generatePerm(List<E> original) {
  if (original.isEmpty()) {
    List<List<E>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    return result;
  }
  E firstElement = original.remove(0);
  List<List<E>> returnValue = new ArrayList<>();
  List<List<E>> permutations = generatePerm(original);
  for (List<E> smallerPermutated : permutations) {
    for (int index = 0; index <= smallerPermutated.size(); index++) {
      List<E> temp = new ArrayList<>(smallerPermutated);
      temp.add(index, firstElement);
      returnValue.add(temp);
    }
  }
  return returnValue;
}
于 2012-04-24T20:19:42.467 に答える
2

問題は、再帰呼び出しを行う前にArrayListのクローンを作成する必要があることです。それ以外の場合は、常に同じArrayListに追加します。

//allPossibleItems is an AL of all items

//this is called with generatePerm(null, new ArrayList<Item>);

private void generatePerm(Item i, ArrayList<Item> a) {
    if (i != null) { a.add(i); }
    if (a.size() == DESIRED_SIZE) {
        permutations.add(a);
        return;
    }
    for (int j = 0; j < allPossibleItems.size(); j++) {
        if (!a.contains(allPossibleItems.get(j))) {
            ArrayList<Item> b = clone(a);
            generatePerm(allPossibleItems.get(j), b);
        }
    }
}
于 2012-04-24T20:11:08.807 に答える