Skip to main content
 首页 » 编程设计

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

2024年12月31日9Leo_wl

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

假设一个多项式可以用两个元素表示: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 的多项式实现可以专门处理这种情况,如果不能,请随意使用。

请您参考如下方法:

你可以很容易地用 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