Определите, какие комбинации векторов будут суммироваться с другим вектором - PullRequest
Новая
       11

Определите, какие комбинации векторов будут суммироваться с другим вектором

0 голосов
/ 02 июля 2018

Я использую Python 3, чтобы попытаться найти, какие линейные комбинации набора векторов будут суммироваться с другим вектором. Я использую массивы в качестве векторов.

Например, у меня был бы целевой вектор и матричный «выбор», содержащий все возможные варианты векторов: 

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

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

Мне нужно что-то, что возвращало бы все возможные комбинации и их целочисленные кратные (нужно, чтобы они были целочисленными), суммировало с целью и игнорировало те, которые не: 

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

Я нашел некоторую информацию о numpy.linalg.solve(x, y), но она не совсем соответствует тому, что я ищу, или я не знаю, как эффективно ее использовать.

1 Ответ

0 голосов
/ 03 июля 2018

Полагаю, что все искомые вами множители положительные.

Вы можете осторожно увеличивать кратные значения, изучая все комбинации, которые дают результаты, не превышающие целевой вектор. 

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]])]
...