从n个元素的数组总和米元件的所有组合的乘法的 [英] Sum of multiplication of all combination of m element from an array of n elements
问题描述
假设我有一个数组 {1,2,5,4}
和 M = 3
。
我需要找到:
Suppose I have an array {1, 2, 5, 4}
and m = 3
.
I need to find:
1*2*5 + 1*2*4 + 1*5*4 + 2*5*4
米元件从n个元素的数组的所有组合的乘法即萨姆
i.e Sum of multiplication of all combination of m element from an array of n elements.
其中一个可能的解决办法是找到所有组合,然后解决它,但是这将是 O(NCM)
解决方案。有没有更好的算法?
One of the solution possible is to find all combination and then solving it but that would be O(nCm)
solution. Is there any better algorithm?
推荐答案
这个问题等价于多项式的第M系数与给定根(计算的韦达定理)。在德尔福适应算法(O(N)内存和O(N ^ 2)时间):
This problem is equivalent to calculation of Mth coefficient of polynom with given roots (Vieta's theorem). Adapted algorithm in Delphi (O(N) memory and O(N^2) time):
function CalcMultiComb(const A: array of Integer; const M: Integer): Integer;
var
i, k, N: Integer;
Coeff: TArray<Integer>;
begin
N := Length(A);
if (N = 0) or (M > N) then
Exit;
SetLength(Coeff, N + 1);
Coeff[0] := -A[0];
Coeff[1] := 1;
for k := 2 to N do begin
Coeff[k] := 1;
for i := k - 2 downto 0 do
Coeff[i + 1] := Coeff[i] - A[k-1] * Coeff[i + 1];
Coeff[0] := -A[k-1] * Coeff[0];
end;
Result := Coeff[N - M];
if Odd(N - M) then
Result := - Result;
end;
调用CalcMultiComb([1,2,3,4],M),其中M = 1..4给予结果10,35,50,24
calls CalcMultiComb([1, 2, 3, 4], M) with M=1..4 give results 10, 35, 50, 24
这篇关于从n个元素的数组总和米元件的所有组合的乘法的的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!