确定在 a、b 和 c 中是否存在数字 n1、n2，使得 n1 + n2 = n3 [ftt，多项式乘法]

Question

您好，我正在解决一个似乎超出我能力范围的问题，因此非常感谢您提供任何提示、阅读材料等方面的建议。这就是问题所在：

给定数字 a、b、c ⊆ {0, ..., n} 的 3 个子集。在 nlog(n) 中检查 a、b 中是否存在数字 n1、n2 和 c 中是否存在 n3，其中 n1 + n2 = n3.

提示我将 a 和 b 转换为多项式系数，并使用 ftt 进行多项式乘法来乘以 a 和 b 的系数。

现在我卡在了多项式乘法的结果之后，接下来我该怎么做？

先谢谢你。

from numpy.fft import fft, ifft
from numpy import real, imag

def polynomial_multiply(a_coeff_list, b_coeff_list):
    # Return the coefficient list of the multiplication 
    # of the two polynomials 
    # Returned list must be a list of floating point numbers.
    # list from complex to reals by using the 
    # real function in numpy
    len_a = len(a_coeff_list)
    len_b = len(b_coeff_list)
    for i in range(len_a-1):
        b_coeff_list.append(0)
    for i in range(len_b-1):
        a_coeff_list.append(0)
    a_fft = fft(a_coeff_list)
    b_fft = fft(b_coeff_list)
    c = []
    for i in range(len(a_fft)):
        c.append(a_fft[i] * b_fft[i])
    inverse_c = ifft(c)
    return real(inverse_c)

# inputs sets a, b, c
# return True if there exist n1 in a, n2 in B such that n1+n2 in C
# return False otherwise
# number n which signifies the maximum number in a, b, c
def check_sum_exists(a, b, c, n):
    a_coeffs = [0]*n
    b_coeffs = [0]*n 
    # convert sets a, b into polynomials as provided in the hint
    # a_coeffs and b_coeffs should contain the result
    i = 0
    for item in a:
        a_coeffs[i] = item
        i += 1
    i = 0
    for item in b:
        b_coeffs[i] = item
        i += 1
    # multiply them together
    c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
    # now this is where i am lost
    # how to determine with c_coeffs?
    return False
    # return True/False

Answer 1

感谢所有提供帮助的人。我想通了，希望这可以帮助遇到类似问题的任何人。我遇到的问题是我错误地分配了 a_coeffs 和 b_coeffs 的系数。

这里是通过测试的解决方案，感兴趣的可以参考。

from numpy.fft import fft, ifft
from numpy import real, imag


def check_sum_exists(a, b, c, n):
    a_coeffs = [0] * n
    b_coeffs = [0] * n
    # convert sets a, b into polynomials as provided in the hint
    # a_coeffs and b_coeffs should contain the result
    for coeff in a:
        a_coeffs[coeff] = 1
    for coeff in b:
        b_coeffs[coeff] = 1
    # multiply them together
    c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
    # use the result to solve the problem at hand
    for coeff in c:
        if c_coeffs[coeff] >= .5:
            return True
    return False
    # return True/False


def polynomial_multiply(a_coeff_list, b_coeff_list):
    # Return the coefficient list of the multiplication
    # of the two polynomials
    # Returned list must be a list of floating point numbers.
    # Please convert list from complex to reals by using the
    # real function in numpy.
    for i in range(len(a_coeff_list) - 1):
        b_coeff_list.append(0)
    for i in range(len(b_coeff_list) - 1):
        a_coeff_list.append(0)
    a_fft = fft(a_coeff_list)
    b_fft = fft(b_coeff_list)
    c = []
    for i in range(len(a_fft)):
        c.append(a_fft[i] * b_fft[i])
    return real(ifft(c))

确定在 a、b 和 c 中是否存在数字 n1、n2，使得 n1 + n2 = n3 [ftt，多项式乘法]

Determining if there exists numbers n1, n2 in a, b and n3 in c such that n1 + n2 = n3 [ftt, polynomial multiplication]

python

algorithm

fft

polynomial-math