🔒 Locked

Complexity

Started by barakat Dec 17, 2004 at 3:57 PM 4 replies 550+ views

Original Post

Dec 17, 2004 at 3:57 PM

as i was trying to solve the subst sum problem and i did this ... i took all the combinations and summed them but these means that if i have n inputs then there are 2^n combinations !!!! this is very ineffecient !! i am sure there is a better way ... :(


bSet setUnion(const bSet & a ,const bSet & b)
{
	bSet s(a);
	for(int i =0 ;i<b.size(); i++)
		s.insert(b);
	
	return s;
}

bSet setPowerset(const bSet& s )
{
    bSet p, t;
	
    if (s.size() == 0)
		return bSet();
    
    if (s.size() == 1) 
		return p;
    
	
    for (int i = s.size()-1; i >= 0; i--) {
		for (int j = 0; j < s.size(); j++) {
			if (j != i)
				t.insert(s[j]);
		}
		p = setUnion(p, setPowerset(t));
		t.clear();
    }
	
    p.insert(s);
	
    return p;
}

iMalc

Dec 17, 2004 at 7:02 PM

Solve what problem? Link or explanation please.

For this:

    bSet p, t;	    if (s.size() == 0)		return bSet();        if (s.size() == 1) 		return p;

Isn't it doing the same thing for "s.size() == 0" and "s.size() == 1"?

Zahlman

Dec 18, 2004 at 2:07 AM

Results 1 - 10 of about 1,030,000 for subset sum problem. (0.20 seconds)

[google]

iMalc

Dec 18, 2004 at 1:40 PM

Oh thanks Zahlman, I was a little confused as to what "subst" meant.
"substitution" perhaps, I thought for example?

Zahlman

Dec 18, 2004 at 8:27 PM

Well it helps that it's a well known "theory" problem for computational complexity, and I took a course in it in university, so the name looked familiar. ;) (*coughhomework?cough*)

eleusive

Dec 18, 2004 at 9:35 PM

Dynamic programming(memoization) is your friend! I'm sure there are more optimizations, but this can speed things up. For input size up to 10 elements, your old code ran indefinatly, but with this technique it ran in a couple of seconds. Here is some code:

std::map<bSet,bSet> m;bSet empty;void setUnion(bSet & a ,const bSet & b){	for(int i =0 ;i<b.size(); i++)		a.insert(b);}bSet setPowerset(const bSet& s ){    if(m[s]!=empty)	return m[s];    bSet p, t;	    if (s.size() == 0)		return m[s]=bSet();        if (s.size() == 1) 		return m[s]=p;    	    for (int i = s.size()-1; i >= 0; i--) {		for (int j = 0; j < s.size(); j++) {			if (j != i)				t.insert(s[j]);		}		setUnion(p, setPowerset(t));		t.clear();    }    p.insert(s);	    return m[s]=p;}

This speeds things up because your function stores the result of all subsets so far encountered, so when the function gets called with the same argument again, the std::map has the results cached so that your function does not have to compute the same thing multiple times. I also made a small optimization in your setUnion function so that the new set is built upon the existing set, which is faster than creating a new set and adding elements to it.

EDIT: actually, you could probrably remove the setUnion function all together and just replace it with p.insert(setPowerset(t)).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.