All possible combinations
Hello,
I am trying to write a java method which takes a hashmap as the input. The hashmap looks as follows:
Key Value
**** ******
Q1 V11,V12,V13,V14....V1n (This is a collection)
Q2 V21,V22,V23,V24....V2n (This is a collection)
.
.
.
.
Qm Vm1,Vm2,Vm3,Vm4....Vmn (This is a collection)
The method should process the hashmap and make all possible combinations as follows:
Combination1: V11, V21, V31.....Vm1
Combination2: V11, V21, V32, V41.......Vm1
and so on.
So basically I am trying to make all possible combinations of the values.
The method will return a collection of these combinations.
I will really appreciate if anybody could shed some light on the logic. I am totally boggled at the moment.
Thanks,
Kunal
[835 byte] By [
kasathea] at [2007-10-1 10:29:41]
> Nope. I have not worked out the size of the resulting
> collection. The size would depend upon the number of
> combinations made after processing the inputted hash
> map.
N items, 2^N combinations. How big is N? If N=20 then you have more than 1,000,000 combinations. This will require at least one reference (4 bytes) per item in each combination. Approx N/2 * 4 * 2^N so for N = 20 you will need at least 40 MBytes.
That is why I ask whether or not you had worked out the size.
Each combination can be represented by an array of bits so it is possible to use a bit map to reduce the memory required but this will slow it down somewhat.
Also, if only sequential access is required then each combination can be expressed as an increment on a binary bit pattern so no memory is require to hold the combinations.
I suppose what I am trying to say is that too much depends on how may items you have and how you are going to use the combinations.
Your in luck. I just wrote this algorithm yesterday and was going to post it because I though it was so useful. This uses a tree to construct all possible <b>unique</b> combinations. This includes combinations of varying amounts (less elements in the set). If this is not what you want, it should give you enough to get going.
First, start with a vector (Collection) and pass a root node (DefaultMutableTreeNode will do)
ResultNode root=new ResultNode(" ");
buildTree(activities,root); //activities is a collection, root is a node
Then we build the tree.
private void buildTree(Vector v, ResultNode node)
{
for (int i=0; i<v.size();i++) {
ResultBinding res=(ResultBinding)v.get(i); //get object from collection
ResultNode newNode=new ResultNode(res); //add as object of node
v.remove(i); //remove this object from collection
Vector newVector=(Vector)v.clone(); // copy collection
node.add(newNode); //add newNode as child
if (newVector.size()>0) //if there is more, recurse
buildTree(newVector, newNode);
}
That's it. So, what you end up with is that each node below the root is a combination where the elements in the combination are all the nodes in the path to the root node (except the dummy root node). I guess if you wanted all combinations of a certain set size, you would go across the tree from left to right at a certain level. And if you wanted all combinations with a size that included all elements, don't remove from the collection but from the cloned collection like this:
...
ResultBinding res=(ResultBinding)v.get(i); //get object from collection
ResultNode newNode=new ResultNode(res); //add as object of node
Vector newVector=(Vector)v.clone(); // copy collection
newVector.remove(i); //remove this object from collection
node.add(newNode); //add newNode as child
if (newVector.size()>0) //if there is more, recurse
buildTree(newVector, newNode);
...
In this case, all left nodes and their paths represent your possible collections. Warning, this could get very big, very fast.
