Starting from a specific number of 1-element sets, I want to pair these sets together (forming 2-elements sets), then pair the paired sets with the original one-element sets (forming 3-elements sets), etc...
For example, if I start with these 1-element sets:
{1}, {2}, {3}, {4}
After pairing them together I will get:
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
Then I pair them with the original 1-element sets and I get
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
and finally
{1, 2, 3, 4}
One important thing that I would like to add is that I will not consider all sets, the new sets need to satisfy some condition, so by the end, I might not have all possible sets.
To solve this problem (efficiently), someone suggested to use trees.
I will form one set at a time, and check if the new set already exists in the tree or not; to do that I will need to have (increasingly) ordered set.
Here's the tree that I will get from running my code (starting with {1}, {2}, {3}, {4}) - assuming there's no constraints on the sets I want to have.
The only reason for this tree is to quickly for duplicates easily.
Is this a relatively efficient way? I will need to start with really large 1-element sets (~100s).
import java.util.LinkedList;
public class TrieTree
{
Node treeNode = new Node();
boolean addInteger(LinkedList<Integer> IntegerToBeAdded)
{
Node startNode = new Node();
startNode = treeNode;
boolean isItNewSet = false;
for(int ix = 0; ix < IntegerToBeAdded.size(); ix++)
{
Integer currInteger = IntegerToBeAdded.get(ix);
int indexOfstartNode = -1;
for(int jx = 0; jx < startNode.children.size(); jx++)
{
if(startNode.children.get(jx).data == currInteger)
{
indexOfstartNode = jx;
break;
}
}
if(indexOfstartNode == -1)
{
Node tempNode = new Node();
tempNode.data = currInteger;
tempNode.parent = startNode;
startNode.children.add(tempNode);
startNode = startNode.children.getLast();
isItNewSet = true;
}
else
{
startNode = startNode.children.get(indexOfstartNode);
}
}
if(isItNewSet)
return true;
else
return false;
}
private class Node
{
public Integer data;
public Node parent;
public LinkedList<Node> children;
Node()
{
children = new LinkedList<Node>();
}
}
}
Main file:
import java.util.LinkedList;
public class Main
{
public static void main(String[] args)
{
TrieTree myTree = new TrieTree();
LinkedList<Integer> originalSet = new LinkedList<Integer>();
originalSet.add(1);
originalSet.add(2);
originalSet.add(3);
originalSet.add(4);
LinkedList<LinkedList<Integer>> totalSet = new LinkedList<LinkedList<Integer>>();
LinkedList<LinkedList<Integer>> currentlyGeneratedSet = new LinkedList<LinkedList<Integer>>();
for(int jx = 0; jx < originalSet.size(); jx++)
{
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(originalSet.get(jx));
// currently generated will be used later so we can add original 1-element sets to it to form more sets
currentlyGeneratedSet.add(temp);
// Add 1-element sets to the total
totalSet.add(temp);
// Add 1-element sets to the tree
myTree.addInteger(currentlyGeneratedSet.get(jx));
}
LinkedList<LinkedList<Integer>> setToBeAddedOn = new LinkedList<LinkedList<Integer>>();
Boolean continueFlag;
do
{
continueFlag = false;
setToBeAddedOn.clear();
// myLastIntegers = myNextLastIntegers; - this way will copy address
// the following way will copy values
//
for(int ix = 0; ix < currentlyGeneratedSet.size(); ix++)
{
setToBeAddedOn.add(currentlyGeneratedSet.get(ix));
}
currentlyGeneratedSet.clear();
for(int j = 0 ; j < originalSet.size(); j++)
{
for(int i = 0; i < setToBeAddedOn.size(); i++)
{
// this will be 1 first time, then 2, then 3, ...
int numberOfAtomicIntegers = setToBeAddedOn.get(i).size();
// itContains will indicate whether the element we want to add already exists or not
// for example adding {1} to {1, 2} will result in a 'true' itContains
//
boolean itContains = false;
// make sure the Integer we want ot add is not already included in the tree
//
if(setToBeAddedOn.get(i).contains(originalSet.get(j)))
itContains = true;
if(!itContains)
{
boolean continueAdding = true;
// currTemp will hold the new set for exmaple;
// when we add {1} to {2, 3}, currTemp will hold {1, 2, 3}
LinkedList<Integer> currTemp = new LinkedList<Integer>();
for(int k = 0; k < numberOfAtomicIntegers; k++)
{
// We need to do the following so that the list is still sorted
//
if(originalSet.get(j) < setToBeAddedOn.get(i).get(k))
{
currTemp.add(originalSet.get(j));
for(int kx = k; kx < numberOfAtomicIntegers; kx++)
currTemp.add(setToBeAddedOn.get(i).get(kx));
continueAdding = false;
break;
}
else
currTemp.add(setToBeAddedOn.get(i).get(k));
}
if(continueAdding)
currTemp.add(originalSet.get(j));
// Here we check if myCurrNewRule exists or not.. we use our tree
//
// addInteger will return 'true' if it's new, 'false' otherwise
boolean isNewRuleExisted = myTree.addInteger(currTemp);
if(isNewRuleExisted /*&& myConstraint here*/)
{
currentlyGeneratedSet.add(currTemp);
totalSet.add(currTemp);
continueFlag = true;
}
}
}
}
}while(continueFlag);
}
}
The goal that I'm trying to accomplish is to form groups of categories taken from attributes of data-sets.
For example, if I have this data-set:
Sex -------- Income ---------- WearsGlasses M ---------- V. High ---------- Yes F ---------- Low -------------- Yes M ---------- High ------------- No F ---------- High ------------- Yes F ---------- V. High ---------- Yes ...
The initial set that I will form is the following (all single categories):
{{sex(M)}, {sex(F)}, {Income(V. High)}, {Income(High)}, {Income(Low)}, {WearsGlasses(Yes)}, {WearsGlasses(no)}}
plus all other single categories that exist in the data-set.
Note: to implement this as explained in the code (using a tree), I will need to give a unique number for each element in my original one-element set mentioned above.
My first condition is that I should have at least a specific number of instances in the data-set for each element in my set. So if I set this number to 2, and if we assume that the shown sample is all the data-set. I will need to remove WearsGlasses(No)
and Income(low)
, since we only have one instance of each.
After this condition is satisfied, I will form two-element sets (surely, only from the one-elements that satisfied my condition)
My second condition is that I can't form new sets that contain same attributes. What I mean is that I can't have: {{Income(High), Income(V. High)}}
, which makes sense because we can't have both at the same time.
So by the end I will have all the possible sets/combinations of all the categories, that occurred more than x number of times (in my example x was 2)
originalSet = {a, b, c}
, when going to 2-elements sets, I might only accept{{a,b}, {a,c}}
and ignore{b,c}
and so on. But I think there should be a way to still efficiently do that; by using power sets. \$\endgroup\$