Извлечение комбинаций из массива numpy, который суммирует до желаемого результата

Question

Я хотел бы вернуть массив или индекс того, который содержит, какие комбинации элементов в массиве numpy суммируют с определенным числом.

Например, если я возьму этот массив и захочунайти все комбинации его членов, которые в сумме равны 7:

import numpy as np

example = np.arange(4) + 1

example
>>> array([1, 2, 3, 4])

он вернет:

somefunction
>>> [[1,2,4], [3,4]]

или индекс:

>>> [[0,1,2], [2,3]]

Я могу представить себеподход с использованием itertools.combinations, хотя я бы хотел избежать этого, потому что набор данных, на котором я пытаюсь использовать это, уже имеет ~ 30 000 членов.Он не работает достаточно быстро при рассмотрении каждой длины комбинаций.

Есть ли более быстрый способ сделать это?

edit: Для получения дополнительной информации мне не обязательно использовать каждую комбинацию30000 членов.Например, я суммирую целые числа до ~ 1000, поэтому мне нужно <1000 составляющих - в моем случае конечное число составляющих списка, вероятно, будет состоять из 100-400 составляющих. </p>

Answer 1

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

Например, с 10k случайными целыми числами от 0 до 10, я нашел 243905016604941663446994 подмножеств, которые составляют до 10 - это 24-значное число.Если бы вы могли перечислить комбинацию каждую наносекунду, это заняло бы более 7 миллионов лет.Число для массива из 30 тысяч случайных целых чисел, суммирующих 1000, должно быть значительно больше.

Фрагмент кода для подсчета комбинаций, суммирующих в число.

import numpy as np
import sys

example = np.arange(4) + 1
example_target = 7

# assuming all elemenst of arr are positive integers
def count_combs(arr, sum_):
    arr = np.sort(arr)

    sys.setrecursionlimit(100_000)
    state_dict = {}

    def state(i, j):
        if (i, j) in state_dict:
            return state_dict[(i, j)]
        elif j < 0:
            res = 0
        elif j == 0:
            res = 1
        elif i == 0:
            res = 1 if j == arr[i] else 0
        else:
            res = state(i - 1, j - arr[i]) + state(i - 1, j)
        state_dict[(i, j)] = res
        return res

    return state(arr.shape[0] - 1, sum_)


# print(count_combs(example, example_target))
# prints 2

test_big = np.random.randint(0, 10, size=10000)
test_target = 10


def test():
    print(count_combs(test_big, test_target))


if __name__ == "__main__":
    test()
    # e.g. 258364297793668558120414

Answer 2

Вы можете использовать, если не возражаете, itertools.combinations:

print([x for i in range(1,4) for x in itertools.combinations(example,i) if sum(x)==7])

Вывод:

[(3, 4), (1, 2, 4)]

Сортировать, если вы хотите заказ, который вы хотите:

print(sorted([x for i in range(1,4) for x in itertools.combinations(example,i) if sum(x)==7]))

Вывод:

[(1, 2, 4), (3, 4)]

Как вы говорите, itertools.combinations будет медленным, но на самом деле не существует другого, более эффективного способа, кроме itertools.combinations tho.