in reply to How to restrict partitions

It seemed wasteful to me to first create all partitions and then filter out the wanted ones. And I wanted to say that it should be simple to draw a partition algorithm that directly does what you want. But it took me longer than I thought... 

use strict;
use warnings;

sub partition {
  my( $n, $level, $max, @part ) = @_;
  $max //= $n;
  $level //= $n;
  my @solutions = $n <= $max ? [ @part, $n ]: ();
  $max = $n-1 if $max > $n-1;
  push @solutions, map { partition( $n-$_, $level-1, $_-1, @part, $_) 
+} reverse 1..$max if $level > 1 and $n > 2;
  return @solutions;
}

my( $number, $depth ) = @ARGV;
my @s = partition $number, $depth;
print "@$_\n" for @s;

[download]

Update: Changed 0..$max to 1..$max.

Update 2: You are not doing this to solve Kakuro puzzles?

Replies are listed 'Best First'.
Re^2: How to restrict partitions
by crunch_this! (Acolyte) on Jan 20, 2014 at 02:27 UTC

    Not kakuro, I'm trying to find polynomials with integer roots whose critical points are also integers. My first idea turned out to create too big a 'haystack' but then I remembered that one of the coefficients of a polynomial is the sum of the zeros. I'm hoping to use them to construct the polynomials I'm interested in. So I figure if I consider the sum of the zeros (the partitions here) it might cut the haystack down quite a bit. At least in the few trial runs I've done it seems to have helped a lot. It wouldn't automatically solve it, I guess you could say it's a "necessary but not sufficient" type of thing where I'd still have to sift through the partitions to find what I'm interested in. An important consideration is that the number of partitions of n increases very quickly, however I'm hopeful that with the restrictions I want to use it will cut down on the amount of stuff I'm not looking for.

    I tried that program but I keep getting 'uninitialized value' errors on $max, $n & $level but I'm not sure how to fix them. I tried tye's attempt below & it seems to work great. It cuts back on a lot of the stuff I'm not looking for but I definitely want to try to get yours working too.

    For example, here's part of what I've been using for a quartic, where is_approximately_an_integer is used to determine whether or not the derivative has roots "close enough" to integers, and poly_roots & poly_derivative are from the Math::Polynomial package:

    grep { is_approximately_an_integer( @$_ ) } [
        poly_roots(
            poly_derivative(
                            
            # expanded form of x*(x - $x)*(x - $y)*(x - $z)
            1, -$x - $y - $z, $x*$y + $x*$z + $y*$z, -$x*$y*$z, 0
            )
        )       
    ];

    [download]
[reply]
[d/l]

      Sorry, this is my fault. I forgot to explain that you need to give the number you want to partition on the commandline and, optionally, also the maximum number of elements.

[reply]

In Section Seekers of Perl Wisdom