I started with the assumption that the partition of 1 was [ [ 1 ] ] and that the partion of each larger one was each sub partion with 1 added to the end, and with one added to each element. Hmm that was more confusing than in my head. Well here, the partition of 2 is [ [ 1 + 1] , [1 , 2]][ [ 1 + 1] , [1 , 1]] and the partition of 3 is [ [ 2 + 1], [1 + 1, 2], [1, 2 + 1], [1 , 2 , 1]]. Well if that hasn't made any sense here is the code.
use strict;
use warnings;
use Data::Dumper;
sub partition {
my $num = shift || 1;
my $temp = [ [1] ];
# updated 0 to 2 in the following,
# since we start with one, the first add_one gets us to two.
$temp = add_one($temp) for (2 .. $num);
return $temp;
}
sub add_one {
my $combinations = shift;
my $temp;
foreach my $combination (@$combinations) {
foreach my $element (@$combination) {
$element++;
push @$temp, [ @$combination ];
$element--;
}
push @$temp, [ @$combination, 1 ];
}
my $hash;
foreach my $combination (@$temp) {
$hash->{ join("-", sort @$combination) }++;
}
return [ map { [ split "-", $_ ] } keys %$hash ];
}
print Dumper(partition(10) );
Oh and I added in some code to stop it from accumulating duplicates.
Updates: Thanks blockhead for noticeing some errors there
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.