python - 没有 Scipy 或 Numpy 的 Python 中的多项式乘法

Question

我正在尝试编写一个函数，将作为输入给出的两个多项式相乘，但我遇到了对系数列表进行排序的问题。

假设一个多项式可以用两个元素表示:idx(指数)和coef(系数)。需要注意的关键是 idx 列表是按指数级排序的，系数是按与各自指数相对应的顺序排序的。

请看下面的示例。

idx1 = [5, 4, 0], coef1 = [1, 2, 3] would represent polynomial1 = x^5+2x^4+3x^0

idx2 = [5, 3], coef2 = [1, 5] would represent polynomial2 = x^5+5x^3

我希望我的函数 mult_coef(idx1, coef1, idx2, coef2) 返回两个列表:idx_mult 和 coef_mult，如下所示:

ideal output:

idx_mult = [10, 9, 8, 7, 5, 3]

coef_mult = [1, 2, 5, 10, 3, 15]

我写了一个函数来获取idx部分:

def mult_idx(idx1, idx2):
    from itertools import combinations, product
    def pairs(*lists):
        for t in combinations(lists, 2):
            for pair in product(*t):
                yield pair

    output = list(set(pairs(idx1,idx2)))
    output = sorted([x+y for x,y in output],reverse=True)
    return sorted(list(set(output)),reverse=True)

#matches ideal idx, but still need coefficients
mult_idx(idx1,idx2) >>> [10, 9, 8, 7, 5, 3]

def mult_coef(idx1, coef1, idx2, coef2):
    coef_output = list(pairs(coef1,coef2))
    coef_output = [x*y for x,y in coef_output]
    return coef_output

#Doesn't match the ideal coefficient output (order is wrong, should be [1, 2, 5, 10, 3, 15])
mult_coef(idx1, coef1, idx2, coef2) >>> [1, 5, 2, 10, 3, 15]

知道如何解决这个问题吗？卡了太久，我不认为 Scipy 或 Numpy 的多项式实现可以专门处理这种情况，如果不能，请随意使用。

Answer 1

你可以很容易地用 defaultdict 解决这个问题(字典可能是多项式的更好表示...poly = {exp: coeff})

from collections import defaultdict

mult = defaultdict(int)  # mult[i] will default to 0

for i1, c1 in zip(idx1, coef1):
    for i2, c2 in zip(idx2, coef2):
        mult[i1 + i2] += c1 * c2

对于您的输入，这给出了

mult = defaultdict(<class 'int'>, {10: 1, 8: 5, 9: 2, 7: 10, 5: 3, 3: 15})

然后您可以将其安排到您感兴趣的列表中:

mult_sorted = tuple(sorted(mult.items(), reverse=True))
idx_mult = [item[0] for item in mult_sorted]
# [10, 9, 8, 7, 5, 3]
coeff_mult = [item[1] for item in mult_sorted]
# [1, 2, 5, 10, 3, 15]

这些都没有经过彻底测试!

---

减少 for 循环的缩进可能更优雅一些:

from itertools import product

for (i1, c1), (i2, c2) in product(zip(idx1, coef1), zip(idx2, coef2)):
    mult[i1 + i2] += c1 * c2