I don't even get what algorithm you try to implement here. But that splitting and joining tells me you are using the wrong data structure if speed is any concern. Also the best (to understand) solution would use recursion but sadly that is not the speediest solution.

Below I use an array to store the latest set and iteratively calculate the next set from that one

The interesting part is how to calculate the next step. The script is rather complicated because I put in some optimizations (a further optimization would be to remember where in the array the row of 2s begin)

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

use strict;
use warnings;

my $sum=80;
my @sets;
my @latest=($sum);
my $higherthan3=0; #the position of the last number higher than 3
my $sumof3sand2s=0; #all the 3s and 2s summed up;

while (1) {

# @latest is always sorted from highest to lowest number
    
#calculate the next set 

    #1: special case 3 3 and a string of 2s
    my $i= $#latest;
    $i-- while ($i>0 and $latest[$i]==2);
    if ($i>0 and $latest[$i]==3 and $latest[$i-1]==3) {
    $latest[$i-1]=2;
    $latest[$i]=2;
    push @latest, 2;
    }
    else {

    #2: get the last number higher than 3. If there is none, stop
    $i= $higherthan3; 
    last if ($i==-1);
    
    #3: if that number is also the last number at all, produce a 2 aft
+er it 
    if ($i==$#latest) {
        $latest[$i]-= 2;
        push (@latest, 2);
        $sumof3sand2s+=2;
        if ($latest[$i]<=3) {
        $higherthan3--;
        $sumof3sand2s+=$latest[$i];
        }
    }
    #4: otherwise cut off at this point, decrease it and put the rest 
    #   to the right of it with the highest possible numbers
    else {
        $#latest=$i;
        $latest[$i]--;
        my $x= $latest[$i];
        my $leftover= $sumof3sand2s+1;
        $sumof3sand2s=0;
        my $foundpoint=0; #is true after the higherthan3 point was fou
+nd
        if ($x<=3) {
        $sumof3sand2s=$x+$leftover;
        $foundpoint++;
        $higherthan3= $i-1;
        }
        while($leftover>$x) {
        $i++;
        if ($leftover>$x+1) {
            push(@latest,$x);
            $leftover-= $x;
        }
        else {
            push @latest, $x-1;
            $leftover-= ($x-1);
            if ($x==4) {
            $sumof3sand2s=3+$leftover;
            $foundpoint++;
            $higherthan3= $i-1;
            }
        }
        }
        if ($leftover>1) {
        push(@latest, $leftover);
        if ($leftover>3) {
            $higherthan3=$#latest;
        }
        elsif (not $foundpoint) { 
            $higherthan3= $#latest-1;
            $sumof3sand2s+= $leftover;
        }
        }
        die "Internal Error" if ($leftover==1);
    } 
    }
    #push @sets, join(',',@latest);
    #print join(',',@latest),"\n";
} 
print join("\n",@sets),"\n";

print @sets+0,"\n";
#------------------

[download]

The script is around 2.5 times faster than JavaFans version, but above $sum==70 memory becomes a problem. That can be avoided by doing further processing of a set in place instead of collecting all sets into an array. But above $sum==100 time will be a constraint too. The numbers (without storing all sets into an array) on my machine:

  n       sets      time
-------------------------
 50       30700     0.37s
 70       500k      4.5s
 75       1M        6.5s
 80       2M        12s
100       21M       2min

[download]

In reply to Re: Decomposing sum to unique sets of summands by jethro
in thread 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.