wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> cs >> Integer sum
(Message started by: birbal on Apr 14th, 2011, 6:04am)

Title: Integer sum
Post by birbal on Apr 14th, 2011, 6:04am
Given a set S of numbers, and a number k, print all permutations of all subsets that sum to k.


Title: Re: Integer sum
Post by birbal on Dec 29th, 2011, 11:40pm
Anybody ??

Title: Re: Integer sum
Post by towr on Dec 30th, 2011, 8:30am
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)

Title: Re: Integer sum
Post by birbal on Jan 7th, 2012, 2:43am

on 12/30/11 at 08:30:51, 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?

Title: Re: Integer sum
Post by towr on Jan 7th, 2012, 11:18am
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.

Title: Re: Integer sum
Post by birbal on Jan 8th, 2012, 8:04am

on 01/07/12 at 11:18:38, 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?

Title: Re: Integer sum
Post by towr on Jan 8th, 2012, 8:13am
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};

Title: Re: Integer sum
Post by birbal on Jan 9th, 2012, 10:40am

on 01/08/12 at 08:13:51, 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.

Title: Re: Integer sum
Post by towr on Jan 9th, 2012, 10:53am
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.)

Title: Re: Integer sum
Post by birbal on Jan 10th, 2012, 5:08am

on 01/09/12 at 10:53:57, 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



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board