9

この操作の名前はありますか？そして：閉じた形の表現はありますか？

  • n個の要素の特定のセット、および1とnの間の値kに対して、
  • k個のアイテムのすべてのサブセット（組み合わせ）を取得します
  • 各サブセットの製品を見つける
  • それらすべての製品の合計を見つける

これはPythonで表現でき、計算は非常に簡単です。

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

セットサイズが大きくなった場合にループを回避するために、閉じた形の式を探しています。

これはこの質問と同じではないことに注意してください。各グループの1つの要素を含むすべての組み合わせの積の合計-この質問は、デカルト積の積の合計に関するものです。サイズkの組み合わせのセットの積の合計を探しています。同じではないと思います。

明確にするために、set（a、b、c、d）の場合、次のようになります。

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

ただ表現を探しています。Pythonコードを具体的に提供する必要はありません。（実装例を提供したい場合は、どの言語でも説明できます。）

4

2 に答える 2

12

これらは基本対称多項式です。ウィキペディアのように合計記号を使用してそれらを書くことができます。根と係数の式を使用して、それらすべてを多項式の係数として一度に取得することもできます（符号まで）

(x-a_1)(x-a_2)...(x-a_k) =
   x^k -
   (a_1 + ... + a_k) x^(k-1) +
   (a_1 a_2 + a_1 a_3 + ... + a_(k-1) a_k)) x^(k-2) +
   ... +
   (-1)^k a_1 ... a_k

（x-a_1）（x-a_2）...（x-a_k）を展開すると、多項式時間アルゴリズムを取得して、これらすべての数値を計算できます（元の実装は指数時間で実行されます）。

編集：Pythonの実装：

from itertools import izip, chain

l = [2,3,4]

x = [1]    
for i in l:
    x = [a + b*i for a,b in izip(chain([0],x), chain(x,[0]))]
print x

これにより、[24、26、9、1]が2 * 3 * 4 = 24、2 * 3 + 2 * 4 + 3 * 4 = 26、2 + 3 + 4=9として得られます。最後の1は空積であり、実装のk=0に対応します。

これはO（N 2）である必要があります。多項式FFTを使用すると、O（N log 2 N）を実行できますが、私はそれをコーディングするのが面倒です。

于 2012-04-11T12:56:52.467 に答える
6

私は他の場所で同じ問題に遭遇したばかりで、もっと簡単な解決策があるかもしれません。基本的にあなたが探している閉じた形はこれです：

（1 + e_1）*（1 + e_2）*（1 + e_3）* ... *（1 + e_n）-1

ここで、集合S = {e_1、e_2、...、e_n}を考慮します。

理由は次のとおりです。

'm'をSの要素の積とします（n = e_1 * e_2 * ... * e_n）。
サブセットの要素の元の積を見ると、それらの積はすべて「m」の約数であることがわかります。
ここで、除数関数を「m」（今後はsigma（m）と呼びます）に1つの変更を加えて適用します。すべてのe_i要素を「素数」と見なします（分割したくないため）。これにより、sigma（e_i ）= e_i+1。

次に、シグマをmに適用すると、次のようになります。

sigma(m)=sigma(e_1*e_2*...*e_n)=1+[e_1+e_2+...+e_n]+[e_1*e_2+e_1*e_3+...+e_(n-1)*e_n]+[e_1*e_2*e_3+e_1*e_2*e_3+...+e_(n-2)]+...+[e_1*e_2*...*e_n]

これが元々の問題でした。（最初の1を除く）。除数関数は乗法であるため、前の方程式は次のように書き直すことができます。

sigma(m)=(1+e_1)*(1+e_2)*(1+e_3)*...*(1+e_n)
ここで必要な修正が1つあります。これは、（最初​​の方程式の最初の）合計に「1」が含まれている空のサブセット（ここでは考慮されていますが、元の問題では存在しません）が原因です。したがって、閉じた形式で必要なのは次のとおりです。
(1+e_1)*(1+e_2)*(1+e_3)*...*(1+e_n) - 1

申し訳ありませんが、実際にコーディングすることはできませんが、計算に2n-1ループを超えることはできないと思います。

（除数関数の詳細については、http：//en.wikipedia.org/wiki/Divisor_functionを参照してください） 。

于 2014-02-03T19:59:08.600 に答える