Re: Looping over ordered partitions

[Max Alekseyev <maxale@gmail.com>]

Hi Charles,

Ordered partitions are called compositions, and they can be generated using the "stars and bars" approach. This is how we can get all compositions of s into k parts:

forvec(v=vector(k-1,i,[0,s]), c=vector(k,i,if(i<k,v[i],s)-if(i>1,v[i-1],0)); print(c); ,1);

Note that zero parts are allowed. If all parts must be positive, then use 

forvec(v=vector(k-1,i,[1,s-1]), c=vector(k,i,if(i<k,v[i],s)-if(i>1,v[i-1],0)); print(c); ,2);

Regards,

Max

On Tue, Feb 6, 2024 at 12:03 PM Charles Greathouse <crgreathouse@gmail.com> wrote:

The looping commands force and forpart are very convenient. I have a problem I was working on which is looking for the smallest vector (in terms of vecsum) with a certain property. What is the best way to perform such a search in PARI/GP?

In my case I have dimension/vector length 11 and sum < 31. (I have an instance with sum 31 but it's probably not optimal.)

I can do a forvec, but even forvec(v=vector(11,i,[1,7]), ...) takes a long time (and spends a lot of time looking at values with sum > 30), and I miss instances with numbers larger than 7. Or else I can use forpart but then I need to permute the values (and in my case I definitely have duplicate values, so naive 11! permutations are wasteful and slow).

(I'm not asking for any new commands here, just the best way to solve my problem at hand.)