Well, if it's a one-off script, perhaps this is the time to learn Prolog, a language which does this sort of thing naturally:
#!/usr/local/bin/perl
use strict;
use warnings;
use AI::Prolog 0.65;
my $by_two = AI::Prolog->make_list(map { $_ * 2 } 1 .. 50);
my $by_five = AI::Prolog->make_list(map { $_ * 5 } 1 .. 20);
my $prolog = AI::Prolog->new(<<"END_PROLOG");
member(X,[X|Tail]).
member(X,[Head|Tail]) :- member(X, Tail).
one_hundred(A,B,C,D,E) :-
or(member(A, [$by_five]), member(A, [$by_two])),
or(member(B, [$by_five]), member(B, [$by_two])),
or(member(C, [$by_five]), member(C, [$by_two])),
or(member(D, [$by_five]), member(D, [$by_two])),
or(member(E, [$by_five]), member(E, [$by_two])),
is(100, plus(A, plus(B, plus(C, plus(D, E))))).
END_PROLOG
$prolog->query('one_hundred(A,B,C,D,E).');
while (my $results = $prolog->results) {
print join(',' =>@{$results}[1 .. 5]), $/;
}
| [reply]
[d/l] |
Wow! That's supposed to illustrate what Prolog is natural for?
All I can say is Ack!
And what would it take to modify it to generate vectors of 6 numbers instead of 5?
Is there a parameter you could simply set?
| [reply] |
To be fair, my example is a bit more verbose than regular Prolog due to some parser limitations that I am currently working through. For example, the member/2 predicate is usually built in and doesn't need to be specified and the last line normally reads like this:
100 is A + B + C + D + E.
There are a few other things that would also clarify this code, but again, the parser is not yet where it should be. However, if you look at the code, you'll notice that I never told it how to find the answer. I just defined logically what the answer was and Prolog figured out how to arrive at it. If you read the code, it actually sounds fairly natural (particularly if you read my example below). It's easy to understand. Your's, on the other hand, is much less clear for me to understand from simply reading it.
I'm also willing to bet that someone with more Prolog-fu than myself would be able to come up with a more concise solution. I just typed in what occurred to me.
Update: And I could just put all of the numbers in one list. That makes the code simpler and faster:
#!/usr/local/bin/perl
use strict;
use warnings;
use AI::Prolog 0.65;
my @numbers = grep { ! ($_ % 2) || ! ($_ % 5) } 1 .. 100;
my $numbers = AI::Prolog->make_list(@numbers);
my $prolog = AI::Prolog->new(<<"END_PROLOG");
member(X,[X|Tail]).
member(X,[Head|Tail]) :- member(X, Tail).
one_hundred(A,B,C,D,E) :-
member(A, [$numbers]),
member(B, [$numbers]),
member(C, [$numbers]),
member(D, [$numbers]),
member(E, [$numbers]),
is(100, plus(A, plus(B, plus(C, plus(D, E))))).
END_PROLOG
$prolog->query('one_hundred(A,B,C,D,E).');
while (my $results = $prolog->results) {
print join(',' =>@{$results}[1 .. 5]), $/;
}
It's also worth noting what my solution can do that your solution cannot do. Tomorrow, your boss comes to you and says "yeah, great, but we just found out that the first and fourth numbers are always 4 and 45, respectively." So I change my query:
$prolog->query('one_hundred(4,B,C,45,E).');
while (my $results = $prolog->results) {
print join(',' =>@{$results}[1 .. 5]), $/;
}
I still get the right answers, but I didn't have to change my code (note that this still requires that the numbers be multiples of 2 or 5, because of the definition. It's trivial to alter, though.)
| [reply]
[d/l]
[select] |
I tend to prefer a recursive approach for things like this; makes it easier to generalize.
The following is kind of brute force, but I think it's correct:
gen( 5, 50, 0, sub { print "@_\n" } );
sub gen
{
my( $cols, $max, $used, $found, @vec ) = @_;
return $found->( @vec, $max-$used ) if $cols == 1;
gen( $cols-1, $max, $used+$_, $found, @vec, $_ )
for 0 .. $max-$used;
}
Update:
I passed 50 for the 'max' value here because it gives the result you want when going to 100 by 2's.
Just multiply every number in every cell of the result by 2.
Similarly, if you want to go to 100 by 5's, pass 20, and multiply all the numbers in the result by 5.
| [reply]
[d/l] |
Here is a simple brute force enumeration for splitting 100 into 5 parts, each a multiple of 2:
my $step = 2;
for (my $a1 = 0; $a1 <= 100; $a1 += $step) {
for (my $a2 = 0; $a2 <= 100-$a1; $a2 += $step) {
for (my $a3 = 0; $a3 <= 100-$a1-$a2; $a3 += $step) {
for (my $a4 = 0; $a4 <= 100-$a1-$a2-$a3; $a4 += $step) {
my $a5 = 100-$a1-$a2-$a3-$a4;
last if $a5 < 0;
print "$a1 $a2 $a3 $a4 $a5\n";
}
}
}
}
If you want to get fancier, such as varying the number of parts, you may want to check out Algorithm::Loops
| [reply]
[d/l] |
could you please specify what you mean by
I'd ideally like to be able to chose to only allow increments of 2 or
+5
if you allow both increments at the same time, then any value after 3 ( = 5 * 2 - 5 - 2 ) is representable as a sum of 2's and 5's, so you might as well go the brute force way, with (0..100) without 1 and 3, cut up to current sum ( sorry, unclear here - basically, use, jdporter's solution, with generate_solutions(1, 100 ...
buth with additional checks, ie, return if ($i == 1 || $i == 3)
if you only want to allow 1 type of increment, say 5, then you might as well generate all partitions of 20 and multiply them by 5. The above solutions either give you only one increment, or, as in Ovid's allow only one of the two to be true, ie, 7 won't be a valid element..
Rethinking further the part about both increments allowed. What about starting with an array (100,0,0,0,0), and then, from the right hand side, try to move either a 2 or 5 to the right, with backtracking recursion, printing any time you succeed without making a negative number. Hmm, but that would make it possible to shift a 2 from a 5, with a remaining 3, which is bad...
Well, ok, I'll stop now.. the above idea, with just shifting 1's, should easily generate all unrestricted partitions of a number in a lexicographic order, so if you only needed 1 increment, it should suffice.. You can probably write the actual code for it faster than I.. in the meantime, I'll start thinking on generating weird restricted partitions... | [reply]
[d/l]
[select] |
In the spirit of TIMTOLanguageTDI, here's a way to do it in Haskell:
partition :: Integer -> Integer -> [[Integer]]
partition total 1 = [[total]]
partition total numparts =
concat $ map (prepend) [total, (total - 1) .. 0]
where
prepend x = map (x:) (subpart x)
subpart x = partition (total - x) (numparts - 1)
-- then:
partition 100 5
Note that this will take a while, as there are over 4.5 million solutions. This doesn't take into account the "only multiples of 2 or 5" criteria, but it's easy to change it so that it does:
partition :: Integer -> Integer -> [[Integer]]
partition total 1 = [[total]]
partition total numparts =
concat $ map (prepend) numlist
where
prepend x = map (x:) (subpart x)
subpart x = partition (total - x) (numparts - 1)
numlist = filter twoorfive [total, (total - 1) .. 0]
twoorfive x = x `mod` 2 == 0 || x `mod` 5 == 0
And this gives about 600k solutions. Much more manageable.
Another way to do it would be to create all possible lists of the desired length (5 in this case), with each element in a given range (0..100 here) and filter out the ones that don't sum to 100. I tried this approach as a mind exercise (you probably wouldn't want to use it because it would be very ineffecient). I got it to work, but only by hardcoding the number of elements to five, using a list comprehension. I know this is a Perl board, but anyone familiar with Haskell know of an easy and intuitive way to do something like:
allLists :: Integer -> Integer -> [[Integer]]
allLists n len = ?
And allLists would return all lists of length len where each element is in the range 0..n?
| [reply]
[d/l]
[select] |
I think "integer partition" is the google phrase you want. | [reply] |
This might help (and it might not)
http://www2.toki.or.id/book/AlgDesignManual/WEBSITE/FILES/GEITIONS.HTM
| [reply] |