4
\$\begingroup\$

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.

example

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)

\$\endgroup\$
5
  • \$\begingroup\$ You want a power set, which can't be that hard. roseindia.net/tutorial/java/core/powerset.html You can then throw out the empty set. Essentially you can loop through {true, false} 4 times and generate each set through inclusion/exclusion. If you want a generator of a set of any size, then use the linked code. \$\endgroup\$
    – Leonid
    Apr 23, 2012 at 4:40
  • \$\begingroup\$ Here is another good approach ... bit fields: geeksforgeeks.org/archives/588 \$\endgroup\$
    – Leonid
    Apr 23, 2012 at 4:47
  • \$\begingroup\$ @Leonid, those are really good suggestions. In my case I will have very large 1-element sets, and I will have a constraint so I I won't be generating the actual power set per say. for example, I might start with 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\$ Apr 23, 2012 at 13:11
  • 1
    \$\begingroup\$ Actually, the best way of doing this really depends on what your condition is. If you tell us more about that we can give better advice. \$\endgroup\$ Apr 23, 2012 at 16:56
  • \$\begingroup\$ @WinstonEwert, I added all the details about my condition. \$\endgroup\$ Apr 23, 2012 at 20:13

1 Answer 1

1
\$\begingroup\$

Firstly, there is a bunch of general stuff that can be cleaned up here:

 boolean addInteger(LinkedList<Integer> IntegerToBeAdded)

You aren't add Integers here. You are adding sets. You should pick better names

    {   
        Node startNode = new Node(); 

        startNode = treeNode;   

Ok, you new a node object, and then throw it away on the next line.

        boolean isItNewSet = false;

Avoid boolean logic flags, they are delayed gotos

        for(int ix = 0; ix < IntegerToBeAdded.size(); ix++)

Use the for-each syntax

        {
            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;
                }
            }

Typically a trie is implemented using an array. Then you can just lookup the proper child node instead of scanning through them.

            if(indexOfstartNode == -1)
            {
                Node tempNode = new Node();

temp is a bad thing to put in a variabe name. All variables are temporary.

                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;

use return isItNewSet;

    }

Similar clean-up is possible on your other code.

Secondly, this whole thing is necessary because you need to check whether a given set has already been generated. But the better solution is to simply not generate duplicate sets. You can use something like this:

void generateSet(Set current, List available)
{
     // make a copy of the available list, removing one item
     available = available.clone();
     Object nextItem = available.pop();

     // generate all sets without that item
     generateSet(current, available); 

     // create a new set with the item
     current = current.clone();
     current.add(nextItem);

     // add to the list of sets
     addSet(current);

     // generate all sets that contain this item
     generateSet(current, available);
}

How to handle the case when the available list goes empty is left as an exercise for the reader. But this technique won't generate the same set twice, so you can avoid checking for it.

For your exact case, you should do something like:

void generateFilter(int feature, Filter filter)
{
     if( feature == filter.featureCount() )
            return;

     generateFilter(feature+1, filter);

     for(int index = 0; index < filter.featureOptions(feature); index++)
     {
          Filter newFilter = filter.addFilter(feature, index);
          if( newFilter.countHighEnough() )
          {
               addToListOfFilters(newFilter);
               generateFilter(feature+1,newFilter);
          }
      }
}
\$\endgroup\$
5
  • \$\begingroup\$ I think I need more help. I think I understand the idea of the function generalSet, but I'm not 100% positive, I tried to run the code to make sure I understand it, but I'm getting errors, mainly on available = availabe.clone(). Even when replacing List with LinkedList<Integer>, I'm still not able to clone. If I do it exactly like you mentioned I'll get the error cannot convert from Object to LinkedList<Integer>. And honestly I don't understand generateFilter function at all :( \$\endgroup\$ Apr 25, 2012 at 17:09
  • \$\begingroup\$ Another question: Typically a trie is implemented using an array. Then you can just lookup the proper child node instead of scanning through them.. I'm interested in this; a lot. I think that's why my code is slow. But the problem is that the children don't always go from 1 to a specific number. For example the children of node 2 (on level 1) are 3 and 4. If I need to create an array for that, it will be from 0 to 4 (0, 1, and 2 will be empty). Won't this cause a problem, since I will have only a small subset of all possible sets? \$\endgroup\$ Apr 25, 2012 at 17:23
  • \$\begingroup\$ @RoronoaZoro, I don't do Java very much so my code was not quite correct. What you need is something like available = (List<Integer>)available.clone(). generateFilter is the same idea, but avoids picking multiple sets from the same category. As for arrays, you still avoid creating the parts of the tree that don't contain anything. It will take more space then before, but that the trade-off with tries. \$\endgroup\$ Apr 25, 2012 at 19:16
  • \$\begingroup\$ Ok, at least right now I know for sure that I shouldn't use a Trie. Since my original 1-element set might be large. From what I understand, if my original set size is 100, and by only going three levels deep, I might need 100^3 spaces (which I think is crazy). I'm currently looking into your suggested way. \$\endgroup\$ Apr 25, 2012 at 19:39
  • \$\begingroup\$ @Roronora: you only allocate what you use: if some node doesn't have a child, you store null, and thus nothing else is allocated down that branch of the tree. Also, if the only possibilities are '3' and '4', then you don't allocate a 5-long array with 3 unused entries: you allocate a 2-long array and subtract 3 every time you do a look-up. \$\endgroup\$
    – user14393
    Jun 24, 2012 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.