Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: How to restrict partitions

by hdb (Monsignor)
on Jan 19, 2014 at 09:50 UTC ( [id://1071173]=note: print w/replies, xml ) Need Help??


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;

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 ) ) ];

      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1071173]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (6)
As of 2024-03-19 09:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found