I hope some kindly monk or three can give me some guidance. I'm trying to decompose an arbitrary sum into a set of summands (or addends or terms, whatever you like to call them), such that there are always at least two summands in the set, and every summand is greater than or equal to 2.

Example; the sum 7 should be broken down into the sets (and only the sets) {5,2}, {4,3} and [3,2,2}. I don't need the permutations i.e. {2,2,3} or {2,3,2} since that would stiffle the speed of another calculation where if one works, all will work. And this needs to be very fast since in use it's going to have to handle sums of up to 10^6.

This is as far as I've gotten, but I just can't seem to get the looping to work quite right:

#!/usr/bin/perl -w
# decompose sums to sets of summands

use strict;
use warnings;
use vars qw($sum $size @temp @summands $prev $next);

$sum = 10;
$prev = 2;
$next = $sum - $prev;

while ($prev <= $next) {
  break();
}

$size += scalar(@summands);

for (my $i = 0 ; $i < $size ; $i++) {
  @temp = split(",",$summands[$i]);
  $sum = pop(@temp);
  $prev = 2;
  $next = $sum - $prev;
  while ($prev <= $next) {
    break();
  }
}

for (@summands) {
  print "$_\n";
}

sub break {
  push(@temp, $prev);
  push(@temp, $next);
  push(@summands, join(",",@temp));
  @temp = ();
  $prev++;
  $next = $sum - $prev;
}

[download]

In reply to Decomposing sum to unique sets of summands by blackmanao

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.