# Generating complete lists of polynomials

I would like to generate a list of all $3$-variable Laurent polynomials with non-negative integer coefficients using a looping construct so that I can, one-by-one, check them for specific specializations.

**Of course, by "all" I mean "all within certain bounds", e.g. on the coefficients, exponents, number of terms... so long as these bounds can be flexibly changed.

Any help would be greatly appreciated.

Sample input/output: Say we want to produce all ordinary (vs. Laurent) polynomials with non-negative integer coefficients in two variables x,y, subject to: Maximum coefficient is $2$ Maximum x and y exponents are $1$

Input> {2,1,1}

Output> 0, 1, 2, x, 1+x, 2+x, 2x, 1+2x, 2+2x, y, 1+y, 2+y, 2y, 1+2y, 2+2y, x+y, 1+x+y, 2+x+y, 2x+y, 1+2x+y, 2+2x+y, x+2y, 1+x+2y, 2+x+2y, 2x+2y, 1+2x+2y, 2+2x+2y, xy, 1+xy, 2+xy, x+xy, 1+x+xy, 2+x+xy, $\ldots$, 2+2x+2xy+2y

for a total of $3^4 = 81$ items in the list. Note that they do not need to be produced in any particular order.

Again, the "output" should be produced via a loop or otherwise, so that I can perform some analysis on one item of the list and then either "terminate" or move to the next item on the list.

For this simplified example, an input of {a,b,c} will produce a list with $(a+1)^{(b+1)(c+1)}$ items.

-
Please give an example of the input and output that you desire. – Mr.Wizard May 4 '14 at 23:13
Sure. I've included a simplified example in the original post. – Ross Elliot May 4 '14 at 23:58

I propose this:

poly[C_, exp_, var_] :=
Times @@@ Tuples[var^Range[0, exp]] //
Tuples[Range[0, C], Length @ #].# &


Test:

poly[2, {1, 1}, {x, y}] // Sort // Short

{0, 1, 2, x, 2 x, 1+x, <<69>>, x+2 y+2 x y, 1+x+2 y+2 x y, 2+x+2 y+2 x y,
2 x+2 y+2 x y, 1+2 x+2 y+2 x y, 2+2 x+2 y+2 x y}


This is also much faster than lp:

lp[1, {3, 2}, {x, y}]   // Timing // First
poly[1, {3, 2}, {x, y}] // Timing // First

0.327

0.015


Allowing even:

poly[2, {3, 2}, {x, y}] // Length // Timing

{2.886, 531441}


## Extension to massive sets

Although not requested here is an approach for extending this code to larger sets. Since huge sets will consume too much memory we could use an incremental approach, relying on IntegerDigits to construct the Dot vectors one at a time. Although this would make generating an entire series slower it allows exploration within a series.

mem : poly[C_, exp_, var_, "VEC"] := mem =  (* memoization *)
Times @@@ Tuples[ var^Range[0, exp] ] // {Length @ #, #} &

poly[C_, exp_, var_, part_] :=
IntegerDigits[part - 1, C + 1, #].#2 & @@ poly[C, exp, var, "VEC"]


Now we can look at e.g. the 5,141,324,824th polynomial in this sequence:

poly[3, {4, 1, 2}, {x, y, z}, 5141324824]

x^3 + x^4 + 3 x^2 y + 2 x^3 y + x^4 y + x^2 z + 3 x^3 z + x^3 y z + x^4 y z +
2 x^2 y z^2 + 2 x^3 y z^2 + 3 x^4 y z^2


Or a list of polynomials in a smaller sequence:

poly[2, {1, 1, 3}, {x, y, z}, {997, 998, 999}] // Column

x z + 2 x y z + x z^2 + 2 x y z^2
x z + 2 x y z + x z^2 + 2 x y z^2 + x y z^3
x z + 2 x y z + x z^2 + 2 x y z^2 + 2 x y z^3


Memoization of the terms vector is included to speed sampling in truly massive sets:

poly[17, {14, 35, 137}, {x, y, z}, 22]
poly[17, {14, 35, 137}, {x, y, z}, 1341]
poly[17, {14, 35, 137}, {x, y, z}, 7^14913] // LeafCount

x^14 y^35 z^136 + 3 x^14 y^35 z^137

4 x^14 y^35 z^135 + 2 x^14 y^35 z^136 + 8 x^14 y^35 z^137

102378

-
@Mr.Wizard...thanks for timings as well...(and much faster as well as neater and clearer)...one day will learn how to be more efficient... – ubpdqn May 5 '14 at 7:54
@ubpdqn You're welcome, and thanks for being gracious. – Mr.Wizard May 5 '14 at 7:58
@ubpdqn Sorry to keep hammering on your code, but since you're open to comments, it looks like my method is also about ten times more memory efficient. – Mr.Wizard May 5 '14 at 8:03
I am very grateful. I will edit my answer to look at your answer. I am grateful that the seeds of the idea are the same (tuples of components and coefficients and assembling...I hadn't appreciated how nice Range and Tuples would work...the inner product was what I wanted to get to but 'bailed' with use of CoefficientRules construct. – ubpdqn May 5 '14 at 8:08
very nice using padded base representation (IntegerDigits) to convert element index to vector. However, should it be IntegerDigits[part - 1, C + 1, #]. As, e.g. for the 81 polynomials of orginal test case: they go from 1 to 81 <-> {0,0,0,0}->{2,2,2,2} (<=>54+18+6+2=80=81-1)? – ubpdqn May 5 '14 at 8:48

EDIT

See Mr. Wizard's answer (better in terms of conciseness, efficiency and memory usage).

Does this achieve your desired result:

lp[r_, exp_, var_] := Module[{num, tup, v},
num = Times @@ (1 + exp);
tup = Tuples[Range[0, r], num];
v = Flatten[Outer[List, ##], Length@exp - 1] & @@ (Range[0, #] & /@
exp);
FromCoefficientRules[#, var] & /@ (Thread[v -> #] & /@ tup)
]


where r is the range of integer coefficients, exp is the list of exponents and var is the variable names.

lp[2, {1, 1}, {x, y}]


yields 81 polynomials:

{0, x y, 2 x y, x, x + x y, x + 2 x y, 2 x, 2 x + x y, 2 x + 2 x y, y,
y + x y, y + 2 x y, x + y, x + y + x y, x + y + 2 x y, 2 x + y,
2 x + y + x y, 2 x + y + 2 x y, 2 y, 2 y + x y, 2 y + 2 x y, x + 2 y,
x + 2 y + x y, x + 2 y + 2 x y, 2 x + 2 y, 2 x + 2 y + x y,
2 x + 2 y + 2 x y, 1, 1 + x y, 1 + 2 x y, 1 + x, 1 + x + x y,
1 + x + 2 x y, 1 + 2 x, 1 + 2 x + x y, 1 + 2 x + 2 x y, 1 + y,
1 + y + x y, 1 + y + 2 x y, 1 + x + y, 1 + x + y + x y,
1 + x + y + 2 x y, 1 + 2 x + y, 1 + 2 x + y + x y,
1 + 2 x + y + 2 x y, 1 + 2 y, 1 + 2 y + x y, 1 + 2 y + 2 x y,
1 + x + 2 y, 1 + x + 2 y + x y, 1 + x + 2 y + 2 x y, 1 + 2 x + 2 y,
1 + 2 x + 2 y + x y, 1 + 2 x + 2 y + 2 x y, 2, 2 + x y, 2 + 2 x y,
2 + x, 2 + x + x y, 2 + x + 2 x y, 2 + 2 x, 2 + 2 x + x y,
2 + 2 x + 2 x y, 2 + y, 2 + y + x y, 2 + y + 2 x y, 2 + x + y,
2 + x + y + x y, 2 + x + y + 2 x y, 2 + 2 x + y, 2 + 2 x + y + x y,
2 + 2 x + y + 2 x y, 2 + 2 y, 2 + 2 y + x y, 2 + 2 y + 2 x y,
2 + x + 2 y, 2 + x + 2 y + x y, 2 + x + 2 y + 2 x y, 2 + 2 x + 2 y,
2 + 2 x + 2 y + x y, 2 + 2 x + 2 y + 2 x y}


3 variable case yields 6561:

lp[2, {1, 1, 1}, {x, y, z}]


-
Perfect. Thanks a million! – Ross Elliot May 5 '14 at 4:42
You have my vote, but see my answer for how this might be done considerably faster. – Mr.Wizard May 5 '14 at 7:50
@RossElliot Mr. Wizard's answer is the better answer...see commentary – ubpdqn May 5 '14 at 8:11