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

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

Answer 1

如果allPossibleItems包含两个不同的元素x和y,那么您将连续将x和y写入列表,直到达到DESIRED_SIZE.那是你真正想要的吗？如果你选择DESIRED_SIZE足够大,你将在堆栈上有太多的递归调用,因此SO异常.

我做的(如果原版没有douplets /重复)是:

  public <E> List<List<E>> generatePerm(List<E> original) {
     if (original.size() == 0) {
       List<List<E>> result = new ArrayList<List<E>>(); 
       result.add(new ArrayList<E>()); 
       return result; 
     }
     E firstElement = original.remove(0);
     List<List<E>> returnValue = new ArrayList<List<E>>();
     List<List<E>> permutations = generatePerm(original);
     for (List<E> smallerPermutated : permutations) {
       for (int index=0; index <= smallerPermutated.size(); index++) {
         List<E> temp = new ArrayList<E>(smallerPermutated);
         temp.add(index, firstElement);
         returnValue.add(temp);
       }
     }
     return returnValue;
   }