Suma produktu podzbiorów
Czy istnieje nazwa tej operacji? I: czy istnieje wyrażenie w formie zamkniętej?
Dla danego zestawu n elementów i wartości k między 1 a n,Weź wszystkie podzbiory (kombinacje) k przedmiotówZnajdź produkt każdego podzbioruZnajdź sumę wszystkich tych produktówMogę to wyrazić w Pythonie i łatwo obliczyć:
from operator import mul
from itertools import combinations
from functools import reduce
def sum_of_product_of_subsets(list1, k):
val = 0
for subset in combinations(list1, k):
val += reduce(mul, subset)
return val
Po prostu szukam wyrażenia w formie zamkniętej, aby uniknąć pętli w przypadku, gdy ustawiony rozmiar będzie duży.
Zauważ, że to NIE jest takie samo jak to pytanie:Suma produktu nad wszystkimi kombinacjami z jednym elementem z każdej grupy - to pytanie dotyczy sumy produktów kartezjańskich. Szukam sumy produktów zestawu kombinacji wielkości k; Nie sądzę, żeby były takie same.
Aby było jasne, dla zestawu (a, b, c, d), a następnie:
k = 4 --> a*b*c*d
k = 3 --> b*c*d + a*c*d + a*b*d + a*b*c
k = 2 --> a*b + a*c + a*d + b*c + b*d + c*d
k = 1 --> a + b + c + d
Po prostu szukam wyrażenia; nie ma potrzeby podawania kodu Pythona specjalnie. (Każdy język będzie ilustracją, jeśli chcesz podać przykładową implementację).