Re: Efficiently finding combinations

<publiustemp-googlegroups@xxxxxxxxx> wrote in message
news:1116529068.999220.121360@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> 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

Imprecise information; are the five numbers unique? (Sure,
your text below assumes they are not, but has "someone"
actually specified this?)

> (no, I don't know why he needed that either.)

Then do ask and let us know.

> 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.

This is a number theoretisk problem. More specifically it
belongs to the theory of partitions, but with a reduced
solution set as stipulated by the divisibilty constraints.
Furthermore, from the given information, we can apply other
contraints which will further reduce the search space,
regardless of whether the five numbers are to be unique
within each partition.

--
Mail sent to this email address is deleted unread
on the server. Please send replies to the newsgroup.


.