Author |
Topic: Integer sum (Read 1743 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Integer sum
« on: Apr 14th, 2011, 6:04am » |
 Quote  Modify
|
Given a set S of numbers, and a number k, print all permutations of all subsets that sum to k.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Integer sum
« Reply #1 on: Dec 29th, 2011, 11:40pm » |
Quote Modify
|
Anybody ??
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer sum
« Reply #2 on: Dec 30th, 2011, 8:30am » |
Quote Modify
|
Are they unique numbers?
You can do it recursively, using a set of numbers you've chosen to include, a set of numbers you have yet to decide about and a remainder that newly included numbers must add up to.
foo(S1, S2, n)
{
if ( n>0)
{
H = S2.val;
foo(S1, S2.next, n);
foo({val: H, next:S1}, S2.next, n-H);
}
if (n == 0) print S1;
}
foo([], S, k)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Integer sum
« Reply #3 on: Jan 7th, 2012, 2:43am » |
Quote Modify
|
on Dec 30th, 2011, 8:30am, towr wrote:Are they unique numbers?
You can do it recursively, using a set of numbers you've chosen to include, a set of numbers you have yet to decide about and a remainder that newly included numbers must add up to.
foo(S1, S2, n)
{
if ( n>0)
{
H = S2.val;
foo(S1, S2.next, n);
foo({val: H, next:S1}, S2.next, n-H);
}
if (n == 0) print S1;
}
foo([], S, k) |
|
How can we make sure that we don't repeat a set if the numbers are not unique?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer sum
« Reply #4 on: Jan 7th, 2012, 11:18am » |
Quote Modify
|
By picking the cases apart where you have 0,1,2,3,etc repeats of a number, rather than just the cases 0 and 1.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Integer sum
« Reply #5 on: Jan 8th, 2012, 8:04am » |
Quote Modify
|
on Jan 7th, 2012, 11:18am, towr wrote:| By picking the cases apart where you have 0,1,2,3,etc repeats of a number, rather than just the cases 0 and 1. |
|
So you mean to say with each number, we also keep a count, both in the original set as well as chosen set. And this number would be >1 for repeated number.
Can't we sort the original set and pick the numbers from it such that we don't end up picking repeated set?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer sum
« Reply #6 on: Jan 8th, 2012, 8:13am » |
Quote Modify
|
What I had in mind is like that, you count each number and treat each number only on one level of the recursion.
So
{1,3,2,3,1,2,1,3,1}
->
{4x1, 2x2, 3x3}
->
foo({}, {4x1, 2x2, 3x3},Sum)
-> for i=0..4
foo ({ix1}, {2x2, 3x3}, Sum-i*1) // first recursion
-> for j=0..2
foo ({ix1, jx2}, {3x3}, Sum-i*1-j*2) // second recursion
-> for k=0..3
foo ({ix1, jx2,kx3}, {}, Sum-i*1-j*2-k*3) // third recursion
->
if Sum-i*1-j*2-k*3 == 0: print {ix1, jx2,kx3};
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Integer sum
« Reply #7 on: Jan 9th, 2012, 10:40am » |
Quote Modify
|
on Jan 8th, 2012, 8:13am, towr wrote:What I had in mind is like that, you count each number and treat each number only on one level of the recursion.
So
{1,3,2,3,1,2,1,3,1}
->
{4x1, 2x2, 3x3}
->
foo({}, {4x1, 2x2, 3x3},Sum)
-> for i=0..4
foo ({ix1}, {2x2, 3x3}, Sum-i*1) // first recursion
-> for j=0..2
foo ({ix1, jx2}, {3x3}, Sum-i*1-j*2) // second recursion
-> for k=0..3
foo ({ix1, jx2,kx3}, {}, Sum-i*1-j*2-k*3) // third recursion
->
if Sum-i*1-j*2-k*3 == 0: print {ix1, jx2,kx3}; |
|
What i was saying is something like this..
Sort the original set
{1,3,2,3,1,2,1,3,1} => {1,1,1,1,2,2,3,3,3}
Now print the subset using the same bitmask approach, just compare the new set with last printed se, if its same, skip it
So what i meant to say is if two bitmasks yield the same subsets, they will occur one after another, so just comparing the current set to be printed with last printed set should avoid repetitions.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer sum
« Reply #8 on: Jan 9th, 2012, 10:53am » |
Quote Modify
|
Yes, but you can avoid even getting to the point where you need to compare one string ready to be printed with the previous one that was printed. That would save a lot of time in the worst case.
Another way to accomplish that, once you sorted them, is to only use a number for inclusion only if it was not excluded before. So the mask for a part where the values are the same, will have zero or more ones followed by zeroes. i.e. for {1,1,1,1,2,2,3,3,3} the first four bits from the mask (corresponding to the 1's) are
0000...
1000...
1100...
1110... and
1111..
(In other words you treat each case with 0,1,2,3,4 1's once.)
|
| « Last Edit: Jan 9th, 2012, 10:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Integer sum
« Reply #9 on: Jan 10th, 2012, 5:08am » |
Quote Modify
|
on Jan 9th, 2012, 10:53am, towr wrote:Yes, but you can avoid even getting to the point where you need to compare one string ready to be printed with the previous one that was printed. That would save a lot of time in the worst case.
Another way to accomplish that, once you sorted them, is to only use a number for inclusion only if it was not excluded before. So the mask for a part where the values are the same, will have zero or more ones followed by zeroes. i.e. for {1,1,1,1,2,2,3,3,3} the first four bits from the mask (corresponding to the 1's) are
0000...
1000...
1100...
1110... and
1111..
(In other words you treat each case with 0,1,2,3,4 1's once.) |
|
True...this solution is better
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print