wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding subsets
        
(Message started by: Wardub on Sep 24^th, 2008, 12:58pm)

Title: Finding subsets
Post by Wardub on Sep 24^th, 2008, 12:58pm

For class we were to write a program that would let users play a game and find subsets that totaled some amount.

How would I write a method that checks to see if it's possible to make a subset sum to some number.
I figure I should just calculate every subset, which would be 2^n. But I can't figure out how to do something like this. I think it should look like a truth table type thing, where if the value is true, you add. Is there an easy algorithm that would allow me to do this?

Title: Re: Finding subsets
Post by towr on Sep 24^th, 2008, 2:08pm

You could use recursion.

I'm gonna use prolog, because that's simplest (for me)

Code:

% base case, empty list has sum 0
subsetsum([], 0).

% can we find subset that gives the sum without 1st element
subsetsum([H|Rest_List], Sum) :- subsetsum(Rest_List, Sum).

% can we find subset that gives the when we include the 1st element
subsetsum([H|Rest_List], Sum) :- RestSum is Sum - H, subsetsum(Rest_List, Rest_Sum).

Title: Re: Finding subsets
Post by Grimbal on Sep 24^th, 2008, 2:16pm

In C, for subsets of up to 64 characters, you can represent them as an integer (long long if necessary).

For example:
int canSum(int size, int[] values, int target)
{
int set; // or long long if necessary
for( set=0 ; set<(1<<size) ; set++ ){
int sum = 0;
for( int i=0 ; i<size ; i++ ){
if( set & (1<<i) ) sum += value[i];
}
if( sum==target ) return 1; // true
}
return 0; // false
}

Of course, there are smarter ways to search.

Title: Re: Finding subsets
Post by Hippo on Sep 24^th, 2008, 2:55pm

It's known NP complete problem so don't expect anything fast.

Title: Re: Finding subsets
Post by Wardub on Sep 24^th, 2008, 4:30pm

on 09/24/08 at 14:16:06, Grimbal wrote:

Thanks, I'm trying to understand this. I really am only familiar with java. Can you tell me what is being passed in as size? And I am unfamiliar with what this means "set<(1<<size)" and "set & (1<<i)" what is the <<? But thanks I'll try and work it out.

Sorry towr, I honestly have no idea what that means. I wish I did, but thanks anyways.

Title: Re: Finding subsets
Post by towr on Sep 25^th, 2008, 12:20am

on 09/24/08 at 16:30:39, Wardub wrote:

what is the <<?

It's a bit-left-shift, also available in Java. 1 << n = 2ⁿ

Quote:

Sorry towr, I honestly have no idea what that means. I wish I did, but thanks anyways.

It's exactly what the comments say, no more and no less. Prolog is a logical programming language, so every statement is a logical statement.

I suppose you can make a fairly literal translation to C/C++/~java.

Code:

bool subsetsum(List alist, int sum)
{

// base case, true if empty list has sum 0
if(alist == NULL)
return sum==0;

return
// can we find subset that gives the sum without 1st element
subsetsum(alist->next, sum)
|| // or
// can we find subset that gives the when we include the 1st element
subsetsum(alist->next, sum - alist->value);
}

Title: Re: Finding subsets
Post by Grimbal on Sep 25^th, 2008, 12:49am

on 09/24/08 at 16:30:39, Wardub wrote:

Can you tell me what is being passed in as size? And I am unfamiliar with what this means "set<(1<<size)" and "set & (1<<i)" what is the <<?

size is the number of values in the array. C unlike Java cannot tell the length of an array.

The idea is to represent a set as an integer. Integers consist of a number of bits (usually 32, it depends on the language and architecture). So have each bit represent one item in the value array.

1 is a single bit. 1<<i is the i'th bit from the right.

1<<size is the number of possible sets. Numbers smaller than that cover all combinations of size bits.

set & (1<<n) is a logical and masking the n'th bit. Set has size bits that can be 1 or 0, (1<<n) has a single bit at position n. set & (1<<n) is non-zero if the n'th bit is set (meaning the n'th element of value is in the set).

Since in C a condition in if( expression ) if true for non-zero expressions, the statement
if( set & (1<<i) ) ...
in effect tests whether the i'th element is in the set.