Re: Efficiently finding combinations

publiustemp-googlegroups@xxxxxxxxx wrote: 
Recently I was trying to figure out the most efficient way of answering
someone's question about finding all combinations of five numbers which
add to 100, given that each number must be divisible by 2 or 5 (no, I
don't know why he needed that either.)  My solution didn't seem very
clean (assumes that Numbers is a list with all of the allowed numbers
to pick from):

  one_hundred(A,B,C,D,E) :-
    number(Numbers),
    member(A, Numbers),
    member(B, Numbers),
    member(C, Numbers),
    member(D, Numbers),
    member(E, Numbers),
    100 is A + B + C + D + E.

That turned out to be rather slow.  Is there a cleaner way of
expressing this?

Also, as a side note, I also couldn't think of an efficient way of
ensuring that (2,2,2,5,85) and (2,2,2,85,5) wouldn't both be
represented, though that wasn't specifically asked for.

Cheers,
Ovid


How about


one_hundred_bis(A,B,C,D,E) :-
        numbers(Numbers),
        member(A, Numbers),
        member(B, Numbers),
        A =< B, AB is A + B, AB < 100,
        member(C, Numbers),
        B =< C, ABC is AB + C, ABC < 100,
        member(D, Numbers),
        C =< D, ABCD is ABC + D, ABCD < 100,
        member(E, Numbers),
        D =< E,
        100 is ABCD + E.

Does it meet your goals ? Can you generalise from that to other
situations ?

Cheers

Bart Demoen
.

Relevant Pages

  • Re: Military Draft
    ... they've got to send more children over to clean up the ... There was a story on CNN last weekend about ... > how the Army's recruitment exceeded their goals for the first time in ... Then they revealed that the Army actually LOWERED its goals in the ...
    (rec.crafts.textiles.quilting)
  • Re: Why we need to drink
    ... We can play a part in ensuring it is clean. ... This is one way we can ensure our water is clean. ...
    (soc.culture.singapore)