如何用python解一道组合题？

Question

我想解一道组合题。给定一个变量列表，我想获得由这些变量组成的具有给定顺序的所有多项式项。例如，对于给定的数字列表 [x1, x2, x3] 和顺序 2，函数应该 return 列表 [x1^2, x1*x2, x1*x3, x2^2, x2*x3, x3^2]；对于给定的数字列表 [x1, x2] 和 3 的顺序，函数应该 return 列表 [x1^3, x1^2*x2, x1*x2^2, x2^3]

如果我在第一个示例中使用 for 循环，代码将如下所示：

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)

但是给定的list的长度和给定的顺序都是不固定的，所以for循环的次数是不确定的。我试图使用递归来解决它但失败了。有人可以帮我解决这个问题吗？

Answer 1

您可以使用 mathmatical induction -

编写 poly(t, order)

如果输入t为空，停止迭代
（归纳法）至少有一个t。如果 order 小于一，则没有任何东西可以展开，return 空多项式
（归纳）至少有一个 t 并且 order 至少有一个。
- 要在组合中包含第一个元素，对于子问题 (t, order - 1) 中的所有 p，将 t[0] 添加到 p 并产生
- 要生成没有第一个元素的所有组合，只需重复子问题(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)

与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

与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

上面我们使用 "*".join(p) 以可读的方式格式化多项式。但是，您可以编写 format 函数将 (x, x) 转换为 x^2 并将 (x, z, z) 转换为 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

Answer 2

不要放弃@Mulan 非常优雅的答案，但是已经有一个内置函数可以代替使用：

import itertools

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

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

如何用python解一道组合题？

How to use python to solve a combination problem?

python

recursion

combinations

loops