递归地生成列表的所有可能排列

Question

我正在尝试以递归方式递归生成列表中的所有项目。我已经看到了一些类似问题的解决方案，但我无法让我的代码正常工作。有人可以指出我如何修复我的代码吗？

这对所有 S/O’ers 开放，而不仅仅是 Java 人员。

（我还应该注意到它因 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);
    }
}

原文由 varatis 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果 allPossibleItems 包含两个不同的元素，x 和 y，那么您连续将 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;
}

原文由 DaveFar 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 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);
        }
    }
}

原文由 Vitaly Olegovitch 发布，翻译遵循 CC BY-SA 4.0 许可协议