用于排列数字列表的Java代码

我编写了一个程序来查找给定项目列表的所有可能的排列。 这恰恰意味着我的程序打印r = 0到n的所有可能的P（n，r）值

以下是代码：

 package com.algorithm; import java.util.ArrayList; import java.util.Calendar; import java.util.Collection; import java.util.HashSet; import java.util.List; import java.util.Set; public class Permutations { public static void main(String args[]) { Permutations obj = new Permutations(); Collection input = new ArrayList(); input.add(1); input.add(2); input.add(3); Collection<List> output = obj.permute(input); int k = 0; Set<List> pnr = null; for (int i = 0; i <= input.size(); i++) { pnr = new HashSet<List>(); for(List integers : output){ pnr.add(integers.subList(i, integers.size())); } k = input.size()- i; System.out.println("P("+input.size()+","+k+") :"+ "Count ("+pnr.size()+") :- "+pnr); } } public Collection<List> permute(Collection input) { Collection<List> output = new ArrayList<List>(); if (input.isEmpty()) { output.add(new ArrayList()); return output; } List list = new ArrayList(input); T head = list.get(0); List rest = list.subList(1, list.size()); for (List permutations : permute(rest)) { List<List> subLists = new ArrayList<List>(); for (int i = 0; i <= permutations.size(); i++) { List subList = new ArrayList(); subList.addAll(permutations); subList.add(i, head); subLists.add(subList); } output.addAll(subLists); } return output; } } 

产量

 P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]] P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]] P(3,1) : Count (3) :- [[3], [1], [2]] P(3,0) : Count (1) :- [[]] 

我的问题是，随着我增加输入列表中的数字。 运行时间增加，输入列表中的11个数字后，程序几乎死亡。 需要大约2 GB内存才能运行。

我在具有8GB RAM和i5处理器的机器上运行它，因此速度和空间不是问题。

如果有人能帮我写一个更有效的代码，我将不胜感激。

Answer 1

如果您想要15个或更多元素的所有排列，请将它们写入磁盘或数据库或其他内容，因为它们不适合内存。 编辑： Steinhaus-Johnson-Trotter算法 。 这可能就是你要找的东西。

Answer 2

如果你没有存储它 – 如果你只是在迭代它 – 那么考虑使用Heap的算法（ http://www.cut-the-knot.org/do_you_know/AllPerm.shtml上的＃3） -或者，为了让您的生活更轻松，请使用Guava的Collections2.permutations ，它实际上并不构建整个排列列表 – 它会动态地遍历它们。 （披露：我向番石榴捐款。）

Answer 3

Google（Guava）的Java库有一个实用方法： Collections2＃permutations（Collection）

Answer 4

您确实意识到您正在生成非常大的列表，并且运行时间将随列表长度的增加而增加。 您确定了给您带来麻烦的清单应该有多长？

可能对某些人有帮助的一件事就是在找到它时打印每个排列，而不是将它们全部收集到列表中然后打印它们。 当然，如果关键是要实际存储整个列表，而不仅仅是打印它们，那将无济于事。