Your skill will accomplishwhat the force of many cannot PerlMonks

### Re: Decomposing sum to unique sets of summands

 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

Create A New User
Node Status?
node history
Node Type: note [id://720098]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2018-03-22 22:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (286 votes). Check out past polls.

Notices?