我在 java 中设计了一个算法，我生成一个列表元素的所有组合。例如，元素 [A, B, C] 它生成组合，[A]，[B]，[C ] , [AB] , [BC] , [ABC] 。或者根据元素 [A, A, B] 生成组合 [A] , [B] , [AA] , [AB] , [AAB] 。
这是我生成组合的代码。
private List<Elemento> combinazioneMassima = new ArrayList<>();
private Log logger = LogFactory.getLog(Combinazioni3.class);
public Combinazioni3(List<Elemento> generaCombinazioneMassima) {
this.combinazioneMassima = generaCombinazioneMassima;
}
public void combine() {
this.findAllCombinations(combinazioneMassima);
}
private static class Node{
int lastIndex = 0;
List<Elemento> currentList;
public Node(int lastIndex, List<Elemento> list) {
this.lastIndex = lastIndex;
this.currentList = list;
}
public Node(Node n) {
this.lastIndex = n.lastIndex;
this.currentList = new ArrayList<Elemento>(n.currentList);
}
}
public void findAllCombinations(List<Elemento> combinazioni) {
Date dataInizio = new Date();
List<List<Elemento>> resultList = new ArrayList<List<Elemento>>();
LinkedList<Node> queue = new LinkedList<Node>();
int n = combinazioni.size();
ArrayList<Elemento> temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(0));
queue.add(new Node(0, temp));
// add all different integers to the queue once.
for(int i=1;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(i));
queue.add(new Node(i, temp));
}
// do bfs until we have no elements
while(!queue.isEmpty()) {
Node node = queue.remove();
if(node.lastIndex+1 < n) {
Node newNode = new Node(node);
newNode.lastIndex = node.lastIndex+1;
newNode.currentList.add(combinazioni.get(node.lastIndex+1));
queue.add(newNode);
}
for(int i=node.lastIndex+2;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
// create a copy and add extra integer
Node newNode = new Node(node);
newNode.lastIndex = i;
newNode.currentList.add(combinazioni.get(i));
queue.add(newNode);
}
GestoreRegole gestoreRegole = new GestoreRegole();
gestoreRegole.esegui(node.currentList);
}
}
但是对于 input > 250 程序停止并且需要很长时间才能完成所有组合。
我怎样才能改进这个解决方案？或者有更好的解决方案吗？
最佳答案
对于input=250，会有这么多的组合: 看这个例子:
(1) {a} => {a}
(3) {a,b} => {a}, {b}, {a,b}
(7) {a,b,c} => {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}
如你所见，会有2^n-1个元素
因此对于输入=250 - 2^250-1 = large number (1.8*10^75)
使用了过多的内存。我觉得20号左右(1048575)也会出事
关于java - 组合算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31269037/