Author |
Topic: Finding subsets (Read 865 times) |
|
Wardub
Junior Member
Gender: 
Posts: 130
|
 |
Finding subsets
« on: Sep 24th, 2008, 12:58pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding subsets
« Reply #1 on: Sep 24th, 2008, 2:08pm » |
Quote Modify
|
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).
|
|
|
| « Last Edit: Sep 24th, 2008, 2:09pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding subsets
« Reply #2 on: Sep 24th, 2008, 2:16pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 24th, 2008, 2:16pm by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Finding subsets
« Reply #3 on: Sep 24th, 2008, 2:55pm » |
Quote Modify
|
It's known NP complete problem so don't expect anything fast.
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Finding subsets
« Reply #4 on: Sep 24th, 2008, 4:30pm » |
Quote Modify
|
on Sep 24th, 2008, 2:16pm, Grimbal wrote: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. |
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding subsets
« Reply #5 on: Sep 25th, 2008, 12:20am » |
Quote Modify
|
on Sep 24th, 2008, 4:30pm, Wardub wrote:It's a bit-left-shift, also available in Java. 1 << n = 2n
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);
}
|
|
|
| « Last Edit: Sep 25th, 2008, 12:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding subsets
« Reply #6 on: Sep 25th, 2008, 12:49am » |
Quote Modify
|
on Sep 24th, 2008, 4:30pm, 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.
|
| « Last Edit: Sep 25th, 2008, 12:50am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print