Author |
Topic: The Sums of a Set (Read 3825 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
The Sums of a Set
« on: Dec 7th, 2003, 9:36am » |
 Quote  Modify
|
You are given a set S [subseteq] {1, ..., n}.
Devise an efficient algorithm that outputs all the numbers (x + y) such that x, y [in] S.
|
|
 IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #1 on: Dec 9th, 2003, 7:12am » |
Quote Modify
|
Can someone give an answer (even the trivial one) ?
Don't worry about how efficent it is, we'll improve it later... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: The Sums of a Set
« Reply #2 on: Dec 9th, 2003, 8:08am » |
Quote Modify
|
on Dec 9th, 2003, 7:12am, Dudidu wrote:| Can someone give an answer (even the trivial one) ? |
|
like
f(S) = {x+y [in] S | (x,y) [in] S[times]S} ?
hmm.. on second thought I don't think I actually know a language that'll pass it (PVS comes close, though it's not so much a programming language as a theorem prover)
Prolog should be simple enough as well though (and reads much the same):
f(S, R):-setof(T, X^Y^(member(X,S), member(Y,S), T is X+Y, member(T,S)), R).
%% in case member isn't predefined
member(E, [E|_]).
member(E, [_|T]):-member(E, T).
|
| « Last Edit: Dec 9th, 2003, 8:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #3 on: Dec 10th, 2003, 12:17am » |
Quote Modify
|
If you didn't understand, you can think of the set S as an array of size m (so getting the elements is as simple as addressing some element in the array).
Now, its seems (to me  ) that its quite easy to give a pseudo-code for the trivial answer.
|
|
IP Logged |
|
|
|
Tom Wang
Newbie
Posts: 3
|
|
Re: The Sums of a Set
« Reply #5 on: Dec 10th, 2003, 1:33am » |
Quote Modify
|
for (int i = 2; i <= 2n; i++)
cout << i << " ";
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #6 on: Dec 10th, 2003, 3:09am » |
Quote Modify
|
on Dec 10th, 2003, 12:54am, towr wrote:| my answer isn't trivial enough? |
|
No, firstly since I don't know Prolog and secondly (the more problematic issue) since I don't know how f(S, R) is practically calculated and thus, I don't know what is its time complexity.
Sorry... 
P.S. - towr, just to be sure does 'member(T,S)' mean that T is a member of S (since if it is, I think that the definition of 'f(S, R)' is incorrect (? ?).
Quote:for (int i = 2; i <= 2n; i++)
cout << i << " "; |
|
Tom Wang, welcome to the forum  .
What did you mean by this loop ?
|
| « Last Edit: Dec 10th, 2003, 3:16am by Dudidu » |
IP Logged |
|
|
|
Tom Wang
Newbie
Posts: 3
|
|
Re: The Sums of a Set
« Reply #7 on: Dec 10th, 2003, 3:54am » |
Quote Modify
|
The program is supposed to output all the numbers z = x + y such that x and y are members of S, given the number n.
|
|
IP Logged |
|
|
|
Tom Wang
Newbie
Posts: 3
|
|
Re: The Sums of a Set
« Reply #8 on: Dec 10th, 2003, 3:58am » |
Quote Modify
|
I was confused by the question; I thought S was the set from 1 to n.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The Sums of a Set
« Reply #9 on: Dec 10th, 2003, 4:21am » |
Quote Modify
|
on Dec 10th, 2003, 3:09am, Dudidu wrote:| No, firstly since I don't know Prolog and secondly (the more problematic issue) since I don't know how f(S, R) is practically calculated and thus, I don't know what is its time complexity. |
|
it should be quadratic
Quote:I guess I just know too many languages.. And it's so tempting to solve problems in the language that solves them the easiest.
Quote:| P.S. - towr, just to be sure does 'member(T,S)' mean that T is a member of S (since if it is, I think that the definition of 'f(S, R)' is incorrect (?:-/?). |
|
Yes that is what it means.
I thought you wanted the sum to be in S.. Apparantly I also misread the problem.. But you can easily remove it..
|
| « Last Edit: Dec 10th, 2003, 6:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #10 on: Dec 10th, 2003, 9:44am » |
Quote Modify
|
on Dec 10th, 2003, 3:58am, Tom Wang wrote:| I was confused by the question; I thought S was the set from 1 to n. |
|
Don't be discouraged, everybody makes mistakes (sometimes)... keep on trying !
on Dec 10th, 2003, 4:21am, towr wrote:| it should be quadratic... |
|
I tought so.
Quote:| I thought you wanted the sum to be in S.. Apparantly I also misread the problem.. But you can easily remove it... |
|
You're right, it is not necessary that the sum will be in S.
Now, the question is how can you improve it (a hint will follow soon (if no one gets it before)...)
|
| « Last Edit: Dec 10th, 2003, 9:44am by Dudidu » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The Sums of a Set
« Reply #11 on: Dec 10th, 2003, 11:56am » |
Quote Modify
|
Here’s a more conventional code that will be easier to discuss the improvements on (at least for me ):
Code:for (sum = 2*S[1]; sum <= 2*S[m]; sum++)
{
for (i = 1; (i <= m) && (S[i] <= sum/2); i++)
{
if ( inS(sum – S[i]) ) { print( sum ); break; }
}
}
|
|
The S[] is the array Dudidu talked about in his other mail; inS() is a membership check. The complexity of this code is O(N*m), which is quadratic in N in the worst case.
One way to improve this code would be to start the inner loop not at 1, but at index k such that sum - S[k] [le] N. However, this doesn’t imrpove the complexity.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #12 on: Dec 10th, 2003, 1:32pm » |
Quote Modify
|
You didn't happen to get the idea for this question from another thread, did you?
I was going to post a link, but I didn't want to give away the answer...
|
| « Last Edit: Dec 10th, 2003, 1:33pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The Sums of a Set
« Reply #13 on: Dec 10th, 2003, 2:49pm » |
Quote Modify
|
on Dec 10th, 2003, 1:32pm, James Fingas wrote:| You didn't happen to get the idea for this question from another thread, did you? |
|
Personally, I haven't made any connection to any existing threads... Thus, the code is as poor as it is.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #14 on: Dec 11th, 2003, 4:07am » |
Quote Modify
|
on Dec 10th, 2003, 11:56am, Barukh wrote:| Here’s a more conventional code that will be easier to discuss the improvements on (at least for me ):... |
|
Barukh hi,
I have some comments/questions about your code:
Quote:| inS() is a membership check... |
|
1) How does it implemented ? - since if it is implemented as a naive search (i.e. looking for that element in S) then it will take O(m2N) and not O(mN)...
Quote:| quadratic in N in the worst case... |
|
2) How can you improve it to be O(m2) (assuming that you fixed the inS() problem/feature )?
3) One remark: you assume that the array S is sorted (which isn't a must) - but this doesn't create a problem (since sorting it would take O(m) ?!).
Waiting for your reply...
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #15 on: Dec 11th, 2003, 4:38am » |
Quote Modify
|
on Dec 10th, 2003, 2:49pm, Barukh wrote:
Personally, I haven't made any connection to any existing threads... Thus, the code is as poor as it is. |
|
I was actually asking Dudidu about the original question. Your code seems fairly straightforward, although there are probably some easier ways to do it.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #16 on: Dec 11th, 2003, 6:02am » |
Quote Modify
|
on Dec 11th, 2003, 4:38am, James Fingas wrote:| I was actually asking Dudidu about the original question... |
|
James hi,
I didn't get the idea for this question from another thread.
But if there is a similar thread and I'm recycling problems, I'm sorry...
P.S. - can you send me the link to the other thread (or post it (after this riddle is solved)) ?
|
| « Last Edit: Dec 11th, 2003, 6:04am by Dudidu » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #17 on: Dec 11th, 2003, 6:09am » |
Quote Modify
|
I guess I'm the only one who sees the similarity. The solution I'm thinking of works in O(n log n). Of course, that's not great if m << n, but pretty cool nonetheless.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: The Sums of a Set
« Reply #18 on: Dec 11th, 2003, 1:11pm » |
Quote Modify
|
on Dec 11th, 2003, 4:07am, Dudidu wrote:| 1) How does it implemented ? - since if it is implemented as a naive search (i.e. looking for that element in S) then it will take O(m2N) and not O(mN)... |
|
Since there were no restrictions on the space, the simplest way is to have a boolean array inS[] - it takes O(N) to build it. Or, even better, use a hash.
Quote:| 2) How can you improve it to be O(m2) (assuming that you fixed the inS() problem/feature )? |
|
I wish I knew...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: The Sums of a Set
« Reply #19 on: Dec 11th, 2003, 10:43pm » |
Quote Modify
|
One thing i don't get in the question,
given any set S with #S=m one can easily find a O(m2) solution.(its just a matter of two loops)
I thought that the knowlege that S is a subset of {1,..,n} would help the case. I came up with O(n*m2log(m)) which hardly seems any better.And my friend seems to suggest that S is a subset of {1,..,n} can hardly ever make the algo efficient because he feels it makes the search space that much bigger.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #20 on: Dec 12th, 2003, 6:02am » |
Quote Modify
|
The trivial answer that is O(m[sup2]) is this one (pseudocode):
input array s of length m
result list Z = empty list
for i = 1 to m {
for j = i+1 to m {
Z.add( s[i] + s[j] )
}
}
This of course has duplicate entries, but if we don't care, it's a trivial O(m[sup2]) answer. I haven't yet thought of a method faster than O(m[sup2]logm) (sort them) to remove the duplicates, so that appears to be the limiting performance factor. So here is a listing of the best times so far:
my interesting solution: O(n log n)
Barukh's solution: O(mn)
my trivial solution: O(m[sup2] log m)
Which of these is best will depend on the relative sizes of m and n. My guess is that an answer running in O(m[sup2]) is possible.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: The Sums of a Set
« Reply #21 on: Dec 12th, 2003, 8:35am » |
Quote Modify
|
hmm on "re-analysis" it seems the method i came up with is O(nmlogm) so it maybe relevant after all.
the procedure is as follows,
Given,
N = {1,...,n}
S subset of N and #S=m
Generate a set A = {2,....,2n}
(Note:this set has all the possible (x+y)'s for x,y belong to N.)
Sort S which is m*logm
Let S' be the set with all the (x+y)'s for x,y belong to S.
int k=0;
for(i=0;i<2n-1;i++)
{
....for(j=0;j<m;j++)
....{
.........if(A[i]>S[j] && A[i]-S[j] is in S)
..............S'[k++] = A[i];
....}
}
the A[i]-S[j] is in S can be done using a binary search algorithm which is O(logm).
So the overall is O(nmlogm)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The Sums of a Set
« Reply #22 on: Dec 12th, 2003, 2:34pm » |
Quote Modify
|
Another way to implement the inS function is just to make an array L (for lookup) that is N long, full of zeros, then do this:
for i = 1 to m {
L[ s[i] ] = 1
}
The inS(j) is L[j], with constant time.
And if you want indentation to work properly, post with indentation screwed up, then modify and resave your post (which fixes indentation).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: The Sums of a Set
« Reply #23 on: Dec 13th, 2003, 6:57am » |
Quote Modify
|
Thanks for that tip off James, that would improve my algo's efficiency to O(mn).
I just realised that my implementation is same as that of Barukh's, the only thing being Barukh has better efficiency since my average efficiency will be always O(mn) and Barukh's average efficiency will be < O(mn).
I think after looking at different directions for better algo i think i would rather vote for the simple O(m2) solution.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: The Sums of a Set
« Reply #24 on: Dec 14th, 2003, 1:04am » |
Quote Modify
|
Everybody hi,
Quote:| The trivial answer that is O(m2) is this one... |
|
James hi,
This is the algorithm that I asked Barukh about. As you indicated it doesn't remove duplicates so... a trivial algorithm would do it (output the desired numbers and remove the duplicates) in an O(m2 + N) (or some may say O(max{ m2,N})) time complexity (which is better then O(mN)) - what is it ?
Nevertheless, I see that you all are fixed on the ~m2 time complexity area so try to improve it... (Big Hint: How polynomials can be used ?).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print