确定哪些向量组合将求和到另一个向量

Question

我正在使用 Python 3 来尝试找出一组向量的哪些线性组合将与另一个向量相加。我正在使用 numpy 数组作为向量。

例如，我有一个目标向量和矩阵 "choices" 包含所有可能的向量选择：

targetvector0 = numpy.array([0, 1, 2])

choices = numpy.array([[0, 1, 0], [0, 0, 1], [0, 0, 2], [1, 1, 0]])

我需要一些东西 return 所有可能的组合和它们的整数倍数（需要它们是整数倍数）总和为目标并忽略那些没有的：

option1 = [[1], [2], [0], [0]]
option2 = [[1], [0], [1], [0]]

我在 numpy.linalg.solve(x, y) 上找到了一些信息，但它并不能完全满足我的需求，或者我不知道如何有效地使用它。

Answer 1

我想你搜索的倍数都是正数。

您可以小心地递增倍数，研究给出的结果不大于目标向量的所有组合。

import numpy as np


def solve(target_vector, choices):
    nb_choices, n = choices.shape
    factors = np.zeros((1, nb_choices), dtype=np.int)
    i = 0

    while True:
        if i == nb_choices - 1:
            return

        factors[0, i] += 1
        difference_to_target = factors.dot(choices) - targetvector

        found_solution = np.all(difference_to_target == 0)
        factors_too_high = np.any(difference_to_target > 0)

        if found_solution:
            yield factors.copy()

        if found_solution or factors_too_high:
            factors[0, :i + 1] = 0
            i += 1
            continue

        i = 0


targetvector = np.array([0, 1, 2])
choices = np.array([[0, 1, 0], [0, 0, 1], [0, 0, 2], [1, 1, 0]])
print(list(solve(targetvector, choices)))
# [array([[1, 2, 0, 0]]), array([[1, 0, 1, 0]])]

确定哪些向量组合将求和到另一个向量

Determine which combinations of vectors will sum to another vector

python

vector

linear-algebra

python-3.x