Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
All,
A problem at Project Euler led me to try and find an extremely fast way of determining the number of unrestricted partitions of an integer. I was suprised to find that nothing on CPAN did this already (or at least I couldn't find anything). So once I solved the problem, I decided to throw together some code and perhaps upload it.

Before I do, I want to solicit your input.

package Integer::Partition::Unrestricted; use strict; use warnings; use Carp; use Math::BigInt; our $VERSION = '0.01'; sub new { my $class = shift; croak "Incorrect number of parameters" if @_ % 2; my $self = bless {}, $class; $self->_Init(@_); return $self; } sub pos { my ($self, $new_pos) = @_; return $self->{POS} if ! defined $new_pos; croak "The 'pos' argument must be a non-negative integer" if $new_ +pos =~ /[^0-9]/; croak "Out of range 'pos'" if $new_pos > $#{$self->{PART}}; return $self->{POS} = $new_pos; } sub last_pos { my $self = shift @_; return $#{$self->{PART}}; } sub val { my ($self, $pos) = @_; my $last = $self->last_pos(); $pos = $last if ! defined $pos; croak "The 'pos' argument must be a non-negative integer" if $pos +=~ /[^0-9]/; return $self->{PART}[$pos] if $pos <= $last; $self->_Add_Partitions($last + 1, $pos); return $self->{PART}[$self->last_pos()]; } sub next { my $self = shift @_; if ($self->pos() < $self->last_pos()) { $self->pos($self->pos() + 1); return $self->val($self->pos()); } $self->_Add_Partitions($self->last_pos() + 1, $self->last_pos() + +1); $self->pos($self->pos() + 1); return $self->val($self->pos()); } sub prev { my $self = shift @_; $self->pos($self->pos() - 1) if $self->pos(); return $self->val($self->pos()); } sub gen_iter { my ($self, $target) = @_; $target = $self->pos() if ! defined $target; croak "The 'gen_iterator' argument must be a positive integer" if +$target =~ /[^0-9]/; my @part = (0, (1) x ($target - 1)); my $done = undef; return sub { return () if $done; my $min = $part[-2]; my $total = $part[0] ? 0 : 1; my $index = 0; for (0 .. $#part - 1) { if ($part[$_] > $min) { $total += $part[$_]; next; } $index = $_; last; } $part[$index]++; $total += $part[$index]; if ($total > $target || $part[$index] > $part[0]) { @part = ($index ? ++$part[0] : $part[0], (1) x ($target - +$part[0])); } else { @part = (@part[0 .. $index], (1) x ($target - $total)); push @part, 1 if $part[0] == 1; } $done = 1 if $part[0] == $target; return @part; }; } sub _Init { my ($self, %opt) = @_; my $n = 1; $n = delete $opt{init} if exists $opt{init}; croak "The 'init' option must be a positive integer" if ! $n || $n + =~ /\D/; croak "Invalid option provided" if %opt; $self->_Set_Defaults(); $self->_Add_Partitions(1, $n); return; } sub _Set_Defaults { my $self = shift @_; $self->{PART} = [ Math::BigInt->new(1) ]; $self->{PENT} = [ 0 ]; $self->{POS} = 0; return; } sub _Add_Partitions { my ($self, $min, $max) = @_; $self->_Add_Pent($max); for my $i ($min .. $max) { my $sum = 0; for my $j (1 .. $self->_Find_Idx($i)) { if (($j % 4) % 3) { $sum += $self->{PART}[$i - $self->{PENT}[$j]]; } else { $sum -= $self->{PART}[$i - $self->{PENT}[$j]]; } } $self->{PART}[$i] = $sum; } return; } sub _Add_Pent { my ($self, $max) = @_; my $need = int(sqrt($max + 1)) * 2 + 1; return if $need <= @{$self->{PENT}}; my $last = $self->_Pent_2_N(); for ($last + 1 .. ($need - 1) / 2) { push @{$self->{PENT}}, ($_ * (3 * $_ - 1) / 2), (-$_ * (3 * -$ +_ - 1) / 2); } return; } sub _Pent_2_N { my $self = shift @_; my $c = $self->{PENT}[-1]; my $x = (1 + sqrt(1 - (4 * 3 * -2 * $c))) / 6; return abs($x) if $x == int($x); return abs((1 - sqrt(1 - (4 * 3 * -2 * $c))) / 6); } sub _Find_Idx { my ($self, $tgt) = @_; my $min = 0; my $max = $#{$self->{PENT}}; my $mid; while ($min <= $max) { $mid = int(($min + $max) / 2); my $val = $self->{PENT}[$mid]; return $mid if $val == $tgt; $tgt < $val ? ($max = $mid - 1) : ($min = $mid + 1); } return $self->{PENT}[$mid] < $tgt ? $mid : $mid - 1; } "This statement is false"; __END__ =head1 NAME Integer::Partition::Unrestricted - Work with unrestricted integer part +itions =head1 VERSION Version 0.01 developed on 2006-02-27 =head1 SYNOPSIS use Integer::Partition::Unrestricted; my $part = Integer::Partition::Unrestricted->new(init => 100); my $last = $part->last_pos(); while ($part->pos() <= $last) { my $pos = $part->pos(); print "$pos = ", $part->val($pos), "\n"; $part->next(); } my $next = $part->gen_iter(10); while (my @part = $next->()) { print "@part\n"; } $part->pos(0); print $part->prev(); =head1 DESCRIPTION This module allows you to work with unrestricted integer partitions =head1 SYNTAX The new() constructor can be called with a hash of additional options my $part = Integer::Partition::Unrestricted->new(); or my $part = Integer::Partition::Unrestricted->new(init => 42); =head1 OPTIONS =over 4 =item init This option allows you to specify an initial number of integer partiti +ons my $part = Integer::Partition::Unrestricted->new(init => 1000); =back =head1 METHODS =head2 pos This method returns the current iterator position if no arguments are +specified. You can set the position any where between 0 and L<"last_pos"> my $curr_pos = $part->pos(); # Set iterator to end of currently calculated partitions $part->pos($part->last_pos()); =head2 last_pos This method returns the position of the last calculated parition my $calculated = $part->last_pos(); =head2 val This method returns the number of partitions of the integer provided a +rgument. It will default to using L<"pos"> if no argument is provided. If the specified value exceed L<"last_pos">, as many new partitions wi +ll be calculated as necessary. # The number of integer partitions of 100 is print $part->val(100), "\n"; =head2 next This method increments L<"pos"> by 1 and returns the number of partiti +ons for that value. It will increment L<"last_pos"> by 1 and calculate th +e next integer partition if necessary. # Set position to end of calculated values my $n = $part->last_pos(); $part->pos($n); # Print number of positions for next integer print $n + 1, " = ", $part->next(), "\n"; =head2 prev This method decrements L<"pos"> by 1 and returns the number of partiti +ons for that value. It will always return 1 at position 0. my $prev_val = $part->prev(); =head2 gen_iter Sometimes it is necessary to know more than just the number of partiti +ons. This method will return an code ref to iterate over the partitions of the integer argument specified. It will default to L<"pos"> if no arg +s are supplied. $part->pos(42); my $next = $part->gen_iter(); while (my @part = $next->()) { print "@part\n"; } =head1 AUTHOR Joshua Gatcomb, <Limbic_Region_2000@Yahoo.com> =head1 ACKNOWLEDGEMENTS This module was inspired by a problem in Project Euler (L<http://mathschallenge.net/index.php?section=project&ref=about>) =head1 BUGS None known. Bug reports, fixes, and feedback are desired. =head1 PERFORMANCE While this module is pure perl and is OO, it is fairly fast and attemp +ts not to waste memory. I am sure there could be plenty of improvements and I w +elcome suggestions (preferrably as patches). =head1 COPYRIGHT Copyright (c) 2006 Joshua Gatcomb. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself. =head1 SEE ALSO The following links may be helpful if you don't know what an integer p +artition is L<http://en.wikipedia.org/wiki/Integer_partition> L <http://mathworld.wolfram.com/Partition.html> =cut
Beyond needing a test suite, I also considered adding a couple of methods to peek at values without changing the position. Feel free to comment on that or any other new methods you think might be useful.

Cheers - L~R


In reply to RFC: Integer::Partition::Unrestricted by Limbic~Region

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



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (9)
As of 2024-03-28 12:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found