Re: Help: How to combine all 4's into least 6's- Is there a way to calculate what the minimum of 6's will be?

gnh888@xxxxxxxxx wrote:
> mensanator@xxxxxxxxxxx
> Thanks for your answer, you got it right.
>
> >> is 21 the minimum (some combinations are duplicated with 21 sets)
>
> Yes this is Exactly what I am looking for.
>
> >> how to write an algorithm that finds the minimum set.
>
> Exactly correct.
>
> >> Didn't you make another post showing a set of 20, or was I
> hallucinating?
>
> Yes absolutely correct. it was showing a set of 20, this set
> of 20 works but this is not my work.
> It was emailed to me 3 years ago.
> I can post the set of 20

Yes, please re-post it.

> but it does not prove this is the lowest
> number we can get.
> I believe we can get 19.

My first algorithm got 21 as the smallest covering set. It's possible
it could do better if I changed some things around to allow more
cases to be checked. I'll play around with it this weekend.

>
> The person who send it to me could not tell me how it was obtained. All
> he mention in a very brief email was that he was using a lot of 1's and
> 0's and was taking a huge amount of time.

Yeah, my program uses a lot of 1s and 0s also. I'll post some
explanations later when I have more time.

>
> This person who emailed me 3 years ago never emailed me back even after
> I send him a few email.
> He send me this URL
> http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml
> The problem I simply can't figure it out how to do what is mentioned on
> the URL.
> This is from a rare book..
> http://iris.gmu.edu/~khoffman/papers/set_covering.html
>
>
> The reason I removed my previous posting was because the question
> looked solved when actually the answer of 20 is not necessarily
> correct.
> I have no way of verifying if 20 is correct and how it was obtained.

That's why I want you to re-post it, I can easily verify whether or not
it is correct.

>
> That person told me he was using a lot of 0and 1 to get this answer.
> and it was taking a huge time to solve that problem.

I believe a brute force check using my algorithm would take 210! or

>>> print gmpy.fac(210)
10582362029223656378427428424334835305758990578716
90195623527375221444875324002101478493690117146739
54768265316577892528273760626189481169051055226066
65074118957389727368479141118013403943916006656189
58385010008177116826257256704776162675986612591949
75646029749546282594356217374097544153589482020891
75077473501255831346084682486417203023912212889600
0000000000000000000000000000000000000000000000000

loops to test all possibilities. Obviously, we don't want to have
to do that. I found 21 simply by testing 210 possibilities.
I'm pondering an open ended scheme that would simply run
forever and track the best answer.

> All I can tell you are the bits and pieces are remember and the only
> part of the email I got left.
>
> The person who send me the email, or did not know how to do it or did
> not want to be bothered with the explanations.
>
> But this is an interesting problem totally genuine.

Definitely. I just completed a program to generate the Cartesian
Product of a set with filters to create the subsets

Permutations with Replacement
Combinations with Replacement
Permutations without Replacement
Combinations without Replacement

Your problem is a case of Combinations without Replacement and
I'm using it to exercise my program.

>
> I'll be happy to post the 20 lines but I believe it will stop people
> form trying to post what I am looking for.

On the contrary, it gives me something to shoot for.

>
> What I am looking for is not the answer of 20 or 19 but the process how
> it is done,

I'll discuss the process in a later post. There is, of course,
no guarantee that my algorithm is the best.

>
> The process must be very interesting. This is what I am after, the
> process and the logic behind it.
> Thanks again for putting your computer to test this?
> I wrote a program but stopped 3 yesr ago because my computyer was not
> powerfull enough.

I'm using Python, which I highly recommend. Very high level. I'll post
the code and explain the logic behind it when I get a chance.

>
> gnh888

.

Relevant Pages

  • That is not the algorithm I proposed
    ... but, yes, my algorithm does require sampling without replacement. ... A PR sequence of 52 cards 52 cards long drawn without repetition is simply a ...
    (sci.crypt)
  • [PATCH/RFT 4/5] CLOCK-Pro page replacement
    ... Implement an approximation to Song Jiang's CLOCK-Pro page replacement ... The algorithm has been extended to handle multiple memory ... +void remember_page(struct page * page, struct address_space * mapping, ...
    (Linux-Kernel)
  • Re: Books on compiler backends?
    ... after you have described the structure of your AST (it does it even without, ... would like to use an algorithm that will do this for me, ... Can I use the standard maximal munch algorithm, with the replacement ... replacement subtrees, indicate that the replacement subtree has cost X ...
    (comp.compilers)
  • Re: [PATCH/RFT 4/5] CLOCK-Pro page replacement
    ... But the fundamental metric for page replacement decision continues to be ... The algorithm has been extended to handle multiple memory ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: Strategy or Iterator?
    ... private int count; ... Dijkstra's algorithm generates permutations, ... All possible subsequences of length N of the input (considered to be ...
    (comp.lang.java.programmer)