Archived

This topic is now archived and is closed to further replies.

Can anyone help me solve this problem?

This topic is 5141 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey there, A few weeks ago, a friend of mine layed out this problem he has been trying to solve - and he turned to me for help. He asked me if I could find an algorithm/implementation to the following problem: Take for example a 5 bit number - there''s a total of 32 combinations: 00000, 00001, 00010, . . . , 11111. Now, from these combinations, select as little combinations as possible so that no matter what combination you choose from the above range - at least 4 bits will match any of your selected combinations. To clarify on that - here''s an example: Take the following combinations: 1) 00000 2) 01011 3) 01110 4) 10101 5) 10111 6) 11010 7) 11101 Total of 7 combinations. No matter which combinations you''ll choose from the range 00000-11111 - you''ll always find at least 4 bits that match one of the selected combination (or more), ie: 00000 - 00000 5 matches(1) 00001 - 00000 4 matches(1) 00010 - 00000 4 matches(1) 00011 - 01011 4 matches(2) 00100 - 00000 4 matches(1) 00101 - 10101 4 matches(4) 00110 - 01110 4 matches(3) 00111 - 10111 4 mathces(5) 01000 - 00000 4 matches(1) 01001 - 01011 4 matches(2) 01010 - 01011 4 matches(2) 01011 - 01011 5 matches(2) 01100 - 01110 4 matches(3) 01101 - 11101 4 matches(7) 01110 - 01110 5 matches(3) 01111 - 01110 4 matches(3) 10000 - 00000 4 matches(0) 10001 - 10101 4 matches(4) 10010 - 11010 4 matches(6) 10011 - 10111 4 matches(5) 10100 - 10101 4 matches(4) 10101 - 10101 5 matches(4) 10110 - 10111 4 matches(5) 10111 - 10111 5 matches(5) 11000 - 11010 4 matches(6) 11001 - 11101 4 matches(7) 11010 - 11010 5 matches(6) 11011 - 11010 4 matches(6) 11100 - 11101 4 matches(7) 11101 - 11101 5 matches(7) 11110 - 01110 4 matches(3) 11111 - 10111 5 matches(5) There are plenty more solutions - but all I need is one... No matter which way I solve it - I always get 8 combinations as the result and not 7 as I showed you above. Now, bear in mind that the algorithm has to work on any number of digits (not necessarily 5), has to work on base 3 numbers to(not just binary - see example below) and be flexible as to allow any number of matching digits, for example: Take again the range above 00000-11111. Select as little combinations as possible so that no matter what combination you choose from the above range - at least 3 bits will match any of your selected combinations. Solution: 1) 00000 2) 11111 Another example: Take the base 3 range: 000, 001, 002, 010, 011, 012, 020, 021, . . . , 222. Select as little combinations as possible so that no matter what combination you choose from the above range - at least 2 Digits will match any of your selected combinations. Solution: 1) 000 2) 112 3) 121 4) 211 5) 222 And finally - the mother of them all... Take the range 00000000000-22222222222 (11 digits, base 3, a total of 177147 combinations). Select as little combinations as possible so that no matter what combination you choose from the above range - at least 9 Digits will match any of your selected combinations. Here the solution has a total of 729 combinations (out of 177147). All of the solutions are the absolute minimal combinations - you wont find any less combinations to satisfy the condition. I need to come up with an algorithm which does this... Any help would be greatl appreciated. ps - give yourself a pat on the back for reading through this post...

Share this post


Link to post
Share on other sites
Yeah, get your friend to post here confirming your tale, then we''ll help. Not meaning to be harsh, but you''ve gotta learn how to think for yourself if it''s homework.



(Stolen from Programmer One)
UNIX is an operating system, OS/2 is half an operating system, Windows is a shell, and DOS is a boot partition virus

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Simplify the problem by changing the numbers. Consider only 3 bit numbers and fewer than 3 bits matching. Possibly even start with 1 bit numbers and work your way up.

Share this post


Link to post
Share on other sites
fredizzimo, Dragon88 - get over yourselves.
I am 25 years old - I''ve been done with homework for quite some time now...
AP - I don''t really understand what you''re saying - could you elaborate on that?
If my description was not clear enough - say so and I will try to explain my problem better

Share this post


Link to post
Share on other sites
No way could this problem be even suggested as homework - It''s way to complicated - just try and solve it yourselves and see how complicated it gets - just try arriving at the "simple" solution of the 7 combos out of the 32 combos and you''ll see what I''m talking about

Share this post


Link to post
Share on other sites
*Note in advance: I have no help for the original posters problem; Sorry *

Ah, homework nazis.
Ive come accross them quite a few times. I always try to simplify my problem as much as possible and remove all the irrelevant clutter surrounding it before I post here, just to avoid having to type out all the background behind what I am doing. But the problem is, what I end up with is a small, concisely worded little problem that seems to have nothing to do with any practical program and therefore people assume it must be a homework question.

Ive never posted a homework question here, except for VERY specific problems I was having, such as "Why is my vector of pointers to Student Objects not supporting polymorphic behavior when I do this..."

Anyway I dont know if this is a homework question or not. It almost seems like one, but he said it wasnt so I believe him and thats all there is to it. Even if it was, its a pretty complicated problem, and this guy obviously didnt get to where he is by getting other people to do his work his whole life, so give him a break and assume he must have tried damn hard before asking this. If you suspect someone is asking a homework question AND you have a problem with that, then I recommend you just dont answer anything. Otherwise you discourage people who would have posted something helpful from posting.
I know its a rule not to post homework stuff, and I agree with that rule. I just think some people here are a little to quick to accuse things of being homework. I only say this because I have been accused of that a few times when it definetly wasnt homework related.

Share this post


Link to post
Share on other sites
AndreTheGiant - Thanks for the backup...
I'll try one more time to explain what I'm looking for - again this is definitly not a "homework problem" for anyone who has that kind of phobia.
I just tried to explain how I saw the problem on my part - but I guess it turned out to be confusing - so here is a simpler/more practical example, that I hope will make more sense:
There are 5 basketball matches that take place. I want to place the least amount of bets on these 5 matches and ensure that I will be correct of at least 4 results -
lets assume home win=0, away win=1 (disregard a draw - thats the base 3 thing I explained in my first post).
The answer to this is 7:
1) 00000
2) 01011
3) 01110
4) 10101
5) 10111
6) 11010
7) 11101
If you test this out - you'll see that if you place these 7 bets on the 5 matches - you are asured of getting at least 4 out of the 5 match results right (you can also say that you'll be wrong of at most 1 match).
the base 3 thing just gets into account the draw case.
What I'm searching for is an algo' that produces this result - the one I came up with does not find the optimum result which is the least amount of bets(combinations) that will satisfy my goal (in this case 7). In the case of this example I always come up with 8 combos instead of 7 - and that applies for all of my calculations:
3 matches (including draw) - I come up with 9(!) while the answer is 5.
6 matches (not including draw) I come up with 16 while the answer is 12.
11 matches (including draw) - I come up with 2187(!!!) while the answer is 729.
I have come across a software that does this calculation, tried to replicate the result - but just can't find my way around it...
I love to solve problems/puzzles and it bugs the hell out of me that I can't find an answer to this (to bad I can't get the source code of that software to check it out).
Again - basically what I'm looking for is a way to find the least amount of bets to place in order to be correct of at least x matches out the total n matches which I bet on.
this problem may seem trivial - but I can guaranty you it's not!!!
If you want - I can post my way of doing it (but this post is getting to long already to throw that in as well).
Thanks again for reading this.

[edit]
I have no idea what my friend needs this for... next time I see him I'll ask him (I think it has to do with some sort of encoding/decoding thing he's working on)
[/edit]

[edited by - NE1 on November 15, 2003 3:24:38 AM]

Share this post


Link to post
Share on other sites
This is probably the least efficient way to do it, but i think it gets the job done...

First find all possible sets of all sizes of the 5 bitstrings

eg:
one set could be:
00000
10001
10010

another set could be:
10001
00100
10011
11101
01010


Then go through and for each of these sets, see if all of the bitstrings 00000 through 11111 can be reached by changing only one of the bits from your test set. If your test set works, keep track of the size of it, and in the end, you solution set is the one of smallest size.

I havent thought this through 100% but if you dont understand what I''m saying, ask and I''ll clarify.

Share this post


Link to post
Share on other sites