recursion地生成列表的所有可能的排列

我试图recursion地生成列表中的所有项目。 我已经看到了类似的问题的一些解决scheme,但我一直无法让我的代码工作。 有人可以指出我可以如何解决我的代码?

这对所有的S / O'er都是开放的,而不仅仅是Java人。

(另外我应该注意,它与SO例外崩溃)。

示例input:[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); } } 

如果allPossibleItems包含两个不同的元素x和y,则连续将x和y写入列表a,直到达到DESIRED_SIZE。 这是你真正想要的吗? 如果selectDESIRED_SIZE足够大,则会在堆栈上有太多的recursion调用,因此SOexception。

我会做什么(如果原来没有douplets / duplicates):

  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; } 
 private List generatePerm(List a, int depth) { // this is the method definition you want // to generate all permutations, you need cycle thru all elements in your list and for each element // add that element to each member of generatePerm(a, depth - 1); // if you want combinations, you need to remove the element and then call /// generateCombinations with the remaining list } 

问题是你必须在进行recursion调用之前克隆 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); } } }