algorithm - N 个数字的所有可能组合

Question

你能帮我做一些算法吗？

我应该找到 N 个数字的所有可能组合:1/N、2/N、3/N、...、N-2/n、N-1/N、N/N

例如取 4 个数字:A、B、C、D

1/4A + B + C + D

2/4A*B + A*C + A*D + B*C + B*D + C*D

3/4A*B*C + A*B*D + A*C*D + B*C*D

4/4:A*B*C*D

我该如何解决这个问题？

Answer 1

如您所见，这些是多项式 (X + A)(X + B)(X + C)(X + D) 展开后的系数。

实现多项式乘以单项式并迭代使用就足够了。

def PolyByMono(Poly, Mono):
    Poly.append(0)
    for i in range(len(Poly) - 2, -1, -1):
        Poly[i + 1]+= Mono * Poly[i]
    Poly[0]+= Mono
    return Poly

def Expand(Numbers):
    Poly= [Numbers[0]]
    for M in Numbers[1:]:
        Poly= PolyByMono(Poly, M)

    print Poly  

Expand([1, 2, 3, 4])

给出:

[10, 35, 50, 24]