I want to solve a combination problem. Given a list of variables, I want to get all the polynomial items with a given order consisting of these variables. For example, for a given list of numbers [x1, x2, x3] and an order of 2, the function should return a list of [x1^2, x1*x2, x1*x3, x2^2, x2*x3, x3^2]; for a given list of numbers [x1, x2] and an order of 3, the function should return a list of [x1^3, x1^2*x2, x1*x2^2, x2^3]

If I use a for loop for the first example, the code will be like:

for i in range(given_order 1):
    for j in range(given_order 1-i):
        for k in range(given_order 1-j-i):
            list.append(x1^i*x2^j*x3^k)

However both the length of the given list and the given order are not fixed, so the number of for loops is uncertain. I tried to use recursion to solve it but failed. Could someone please help me with this problem?

CodePudding user response：

You can write poly(t, order) using mathmatical induction -

1. if input t is empty, stop iteration
2. (inductive) there is at least one t. if order is less than one, there is nothing left to expand, return the empty polynomial
3. (inductive) there is at least one t and order is at least one.
   • To include the first element in combinations, for all p in the sub-problem (t, order - 1), prepend t[0] to p and yield
   • To generate all combinations without the first element, simply recur on the sub-problem (t[1:], order)

def poly(t, order):
  if not t:
    return                        #1
  elif order < 1:
    yield ()                      #2
  else:
    for p in poly(t, order - 1):  #3
      yield (t[0], *p)
    yield from poly(t[1:], order)

With order = 2 -

for p in poly(('x', 'y', 'z'), 2):
  print("*".join(p))

x*x
x*y
x*z
y*y
y*z
z*z

With order = 3 -

for p in poly(('x', 'y', 'z'), 3):
  print("*".join(p))

x*x*x
x*x*y
x*x*z
x*y*y
x*y*z
x*z*z
y*y*y
y*y*z
y*z*z
z*z*z

Above we use "*".join(p) to format polynomials in readable way. You could however write a format function to convert (x, x) to x^2 and (x, z, z) to x*z^2 -

def format(p):
  mem = dict()
  for x in p:
    mem[x] = mem[x]   1 if x in mem else 1
  return "*".join(x if e == 1 else f"{x}^{e}" for (x,e) in mem.items())

for p in poly(('x', 'y', 'z'), 3):
  print(format(p))

x^3
x^2*y
x^2*z
x*y^2
x*y*z
x*z^2
y^3
y^2*z
y*z^2
z^3

CodePudding user response：

Not to take away from @Mulan's very elegant answer, but there is already a built-in function that you can use instead:

import itertools

order = 3
var = ['x', 'y', 'z']

c = itertools.combinations_with_replacement(var, order)
for i in c:
   print(i)