pasquale.restaino1992
BAN USER- -1of 1 vote
AnswersI realized this algorithm for generating combinations. It works in the following way, if we have the input:
- pasquale.restaino1992 in United States
[A, B, C]
The combinations will be
[A], [B], [C]. [A, B], [A, C], [B, C], [A, B, C].
While if we have in input:
[1,1,2,3]
The combinations will be:
[1], [2], [3], [4], [1,2], [1,3], [2,3 ], [1,1,2,3].
However, this algorithm has a running time of good only when the input is a list of size 4, if the list is of size 5 or more (when there are 5 different elements ( for example 80 A, 150 B , 80 C , 30 D , 20 E)) the program stops and gives me java.lang.OutOfMemory (I increased the memory for in java). One problem could be the fact that I have used LinkedList, but I'm not sure.
Is there a better solution?
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);
}
}| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm - -1of 1 vote
AnswersI realized this algorithm for generating combinations. It works in the following way, if we have the input:
- pasquale.restaino1992 in United States
[A, B, C]
The combinations will be
[A], [B], [C]. [A, B], [A, C], [B, C], [A, B, C].
While if we have in input:
[1,1,2,3]
The combinations will be:
[1], [2], [3], [4], [1,2], [1,3], [2,3 ], [1,1,2,3].
However, this algorithm has a running time of good only when the input is a list of size 4, if the list is of size 5 or more (when there are 5 different elements ( for example 80 A, 150 B , 80 C , 30 D , 20 E)) the program stops and gives me java.lang.OutOfMemory (I increased the memory for in java). One problem could be the fact that I have used LinkedList, but I'm not sure.| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm - 0of 0 votes
AnswersHello , I must write a program that given the elements in a list , generates all combinations of these elements .
- pasquale.restaino1992 in United States
For example, if I [A, B , C ] , the possible combinations are [ A] , [B ] , [ C ] , [A, B ] . [ A, C ] , [ B, C ] , [A, B , C ] . Another example , having [ A, A, B] the possible combinations are [ A] , [ A, A ] , [A, B ] , [ A, A, B, A ] .
How can I write it in java ?| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersmy algorithm generates combinations of elements . For example having [A , B , C ] creates the following combinations [ A] , [ B ] , [ C ] , [ AB ] , [ AC ] , [ B , C ] , [ ABC ] . Unfortunately for items too large too long and too much memory space . So many times I java.lang.OutOfMemory launches . How can I fix ?
- pasquale.restaino1992 in United States
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 List<List<Elemento> > 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);
}
Date dataF = new Date();
long tempo = dataF.getTime() - dataInizio.getTime();
logger.info ("durata genera combinazioni: " + tempo);
return resultList;| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersHello , I must write a program that given the elements in a list , generates all combinations of these elements .
- pasquale.restaino1992 in United States
For example, if I [A, B , C ] , the possible combinations are [ A] , [B ] , [ C ] , [A, B ] . [ A, C ] , [ B, C ] , [A, B , C ] . Another example , having [ A, A, B] the possible combinations are [ A] , [ A, A ] , [A, B ] , [ A, A, B, A ] .
How can I write it in java ?| Report Duplicate | Flag | PURGE
Java - 0of 2 votes
AnswersI have this element {1, 1, 2, 3}, so i have an duplicate element. I want generate combinations and my result should be: {1} {2} {3} {1 1} {1 2} {1 3} {2 3} {1 1 2} {1 1 3} {1 2 3} {1 1 2 3}. The order of element isn't important, {1 1 2 3} == {2 3 1 1}, but i wan't a duplicate result set.
- pasquale.restaino1992 in United States
My code is:
enter code herepublic List> powerSet1(List originalSet) { Date inizio = new Date(); int resultSize = (int) Math.pow(2, originalSet.size()); // resultPowerSet is what we will return List> resultPowerSet = new ArrayList>(resultSize);
// Initialize result with the empty set, which powersets contain by definition
resultPowerSet.add(new ArrayList<Elemento>(0));
// for every item in the original list
for (Elemento itemFromOriginalSet : originalSet) {
// iterate through the existing powerset result
// loop through subset and append to the resultPowerset as we go
// must remember size at the beginning, before we append new elements
int startingResultSize = resultPowerSet.size();
for (int i=0; i<startingResultSize; i++) {
// start with an existing element of the powerset
List<Elemento> oldSubset = resultPowerSet.get(i);
// create a new element by adding a new item from the original list
List<Elemento> newSubset = new ArrayList<Elemento>(oldSubset);
newSubset.add(itemFromOriginalSet);
// add this element to the result powerset (past startingResultSize)
resultPowerSet.add(newSubset);
}
}
logger.info(resultPowerSet);
Date fine = new Date();
long tempo = fine.getTime() - inizio.getTime();
logger.info ("durata genera combinazioni: " + tempo);
return resultPowerSet;
}
But this generate duplicate.| Report Duplicate | Flag | PURGE
Java Developer Java
Hi, thank you. Can you help me write it in java ? It also works for a big list ? Because to me for n > 25 launches an exception java.lang.OutOfMemory
- pasquale.restaino1992 May 25, 2015
Thank you very much. But this is a problem. for an input of size > 87 java trows java.lang.OutOfMemory . I I need an algorithm that does not bowl except for input = 342 elements .
- pasquale.restaino1992 May 26, 2015