|
||
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:
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:
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 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:
True...this solution is better |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |