Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re: Decomposing sum to unique sets of summands

by blokhead (Monsignor)
on Oct 28, 2008 at 20:26 UTC ( #720098=note: print w/replies, xml ) Need Help??

in reply to Decomposing sum to unique sets of summands

Here is a slightly simpler iterator than jethro's, but surely it's doing the same thing. It avoids the recursion blowup of JavaFan.
sub iterator { return unless @_; my @p = ($_[0]); return sub { ## collect all the trailing 2s, and last trailing 3 if present my $temp = 0; $temp += pop @p while @p and $p[-1] == 2; $temp += pop @p if @p and $p[-1] == 3; ## updated return if ! @p; ## reduce the last guy by 1, avoid total of 1 leftover $p[-1]--, $temp++; $p[-1]--, $temp++ if $temp == 1; ## redistribute collected amount, as large as possible ## (largest increments can be $p[-1]) if ($temp % $p[-1] == 0) { push @p, ($p[-1]) x ($temp/$p[-1]); ## special case to avoid 1 leftover } elsif ( $temp % $p[-1] == 1 ) { my $m = int ($temp/$p[-1]) -1; push @p, ($p[-1]) x $m, $p[-1]-1, 2; } else { my $m = int ($temp/$p[-1]) ; push @p, ($p[-1]) x $m, ($temp - $p[-1]*$m); } @p; } } my $iter = iterator(shift || 50); while (my @part = $iter->()) { print "@part\n"; }
Like jethro's, there could be some efficiencies gained by keeping track of some pointers, but the main problem is that there are just so many partitions. So I think the problem statement should be clarified, especially if 10^6 is involved.

Update: updated the marked line according to BrowserUk's suggestion. (added "@p and").


Replies are listed 'Best First'.
Re^2: Decomposing sum to unique sets of summands
by BrowserUk (Pope) on Oct 29, 2008 at 02:04 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://720098]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (2)
As of 2021-02-25 00:04 GMT
Find Nodes?
    Voting Booth?

    No recent polls found