Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Sloane's Integer Sequences gives the number for partitions of N for many values of N. The first solution given in this thread (and the one in its reply) doesn't work. For instance, with N=10, it only gives 42 when it should give 77 (among other obviously invalid partitions it lists).

Here's one using an iterator. Since the number of partitions of N grows exponentially with N, it might be best to not have the entire set of partitions in memory. This is based off the algorithm outlined here.

my $n = shift || 10; my $iter = int_partitions($n); my $total; while ( my @part = $iter->() ) { $total++; print "@part\n"; } print "There are $total partitions of $n\n"; sub int_partitions { my $n = shift; my @tally; return sub { if (!@tally) { @tally = ( (0) x $n, 1 ); return ($n); } ## last partition is $n 1's return if $tally[1] == $n; ## take one away from smallest >1 part my ($least) = grep { $tally[$_] } 2 .. $n; $tally[$least]--; $tally[$least-1]++; $tally[1]++; ## collect multiple 1's into groups smaller than $least while ( $least > 2 and $tally[1] > 1 ) { my $move = ( sort { $a <=> $b } $least-1, $tally[1] )[0]; $tally[1] -= $move; $tally[$move]++; } return map { ($_) x $tally[$_] } reverse 1 .. $n; }; }
This returns partitions in decreasing lexicographic order. Cheers!

Update: Just for fun, here's code for iterating over all partitions of a set (also inspired from the article linked above):

my @set = @ARGV ? @ARGV : 1 .. 4; my $iter = set_partitions(@set); my $total; while ( my @part = $iter->() ) { $total++; print join(" ", map { "[@$_]" } @part), $/; } print "There are $total partitions of @set\n"; sub set_partitions { my @universe = @_; my @growth; return sub { if (!@growth) { @growth = (0) x @universe; return [ @universe ]; } return if $growth[-1] == $#growth; my $i = $#growth; $growth[$i--] = 0 while $growth[$i-1] == $growth[$i] - 1; $growth[$i]++; my @return; push @{ $return[$growth[$_]] }, $universe[$_] for 0 .. $#growt +h; return @return; }; }
The internal order of parts is not significant. The parts are returned in ascending order of their smallest element. If the input set has duplicates, so will the output. I'd have to think about how to do this for multisets... Hey, this is fun! ;)


In reply to Re: Generator of integer partitionts of n by blokhead
in thread Generator of integer partitionts of n by chiburashka

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, 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, 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.
  • Log In?

    What's my password?
    Create A New User
    [shmem]: trying to build a RPM for some perl with a bunch of modules. Trying perlbrew, trying alien.
    [stevieb]: finally got my 12v solar setup for my Pi/Arduino, with a 12v 7.2Ah battery. Testing how long the Pi will run on the fully charged battery before I hook it up to the solar regulator. I expect between 8 and 18 hours, depending on load.
    [shmem]: ...writing a Makefile for that. Edit, test, lather, rinse, repeat.

    How do I use this? | Other CB clients
    Other Users?
    Others perusing the Monastery: (7)
    As of 2017-03-25 22:23 GMT
    Find Nodes?
      Voting Booth?
      Should Pluto Get Its Planethood Back?

      Results (313 votes). Check out past polls.