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

一尘不染

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

algorithm

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

它对所有S / O员工开放，而不仅仅是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);
      }
  }

阅读 324

2020-07-28

共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;
   }

2020-07-28