[Macaulay2] Defining a function revursively

[Venkitesh S.]

Hi!

I am trying to compute an array of all n-tuples (as arrays) [a_1,...,a_n] of nonnegative integers satisfying \sum_i a_i = w and a_i <= b_i, for every i, for fixed b_1,...,b_n.  The function is supposed to have w,b_1,...,b_n as arguments.  The following is my attempt.  I have considered the arguments w and x, where x = [b_1,...,b_n].  I am trying to compute recursively.  However, the recursion does not seem to work.  I get an empty array [] as output when x is not a singleton array.  Any advice would be appreciated.

Code:

f = (w,x) -> (
if w < 0 then return []
else
if #x == 1 and w <= last x then return [[w]]
else
if #x == 1 then return []
else
g = [];
y = drop(x,-1);
t = min{w,last x};
for i from 0 when i <= t do (
h = f(w-i,y);
for j from 0 when j < #h do g = append(g,append(h_j,t));
);
return g
)

Thanks,

Venkitesh

[Michael Burr]

Can you provide an example where you're getting an empty array?  I tried f(2,[3,4,5]) and didn't get an empty array (although the result was not the intended result).

[Michael Burr]

How about this code: 

g = (w,x) -> (

  if length x == 0 then {}

  else if length x == 1 then ( if first x >= w then {{w}} else {})

  else flatten apply(min(w,first x)+1,i->apply(g(w-i,drop(x,1)),j->if length j > 0 then prepend(i,j)))

  )

f = (w,x) -> new Array from apply(g(w,x),i->new Array from i)

If you're ok with a list of lists, then f isn't even needed.

[Venkitesh S.]

Hi Michael, 

The example where I was getting an empty array was w = 7 and x = [3,4,3,2,1].

The modified code given by you works well.  Thank you!

Regards,

Venkitesh

--
You received this message because you are subscribed to the Google Groups "Macaulay2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaulay2+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/macaulay2/e8a234eb-d2a3-44c6-a5ae-e202d9e1d8ebn%40googlegroups.com.