计算所有排序数组组合的平均值

Question

我需要得到 n choose k 绘图在排序数组中的统计期望值。

举个例子，假设我想从下面的排序数组中选择 2 个元素

[1, 2, 3]

所有可能组合的集合如下：

(1, 2)
(1, 3)
(2, 3)

所以第一个元素的期望值为(1 + 1 + 2) / 3 = 1.33，第二个元素的期望值为(2 + 3 + 3) = 2.67

这是一个使用暴力破解方法的函数，但在大型数组上使用它太慢了。有smarter/faster方法吗？

import itertools
import math
def combinations_expected_value(arr, k):
    sums = [0] * k
    l = math.comb(len(arr), k)
    for comb in itertools.combinations(arr, k):
        for i in range(k):
            sums[i] += comb[i]
    
    return [sums[i] / l for i in range(k)]

谢谢！

Answer 1

对于组合中的每个位置，可能的值是从该位置开始到最后一个 k-p-1 元素的列表子集。例如对于 1..100 中 6 的组合，位置 3 只能包含值 3..96

对于 positon/value 对中的每一对，出现次数将是左侧元素组合与右侧元素组合的乘积。

例如，对于 1..100 列表中的 6 个元素的组合，45 出现在第三个位置的次数是 2 in 1..44 的组合乘以 3 in 46 的组合..100。所以我们将有 C(44,2) * C(55,3) * 45 positon/value 对。

您可以对每个 positon/value 对重复此计算，以获得输出组合中每个位置的总数。然后将这些总数除以组合数得到 expected value:

from math import comb

def countComb(N,k):
    result = [0]*k
    for p in range(k):                 # p is count on the left
        q = k-p-1                      # q is count on the right
        for i in range(p,len(N)-q):
            left  = comb(i,p)          # combinations on the left >= 1
            right = comb(len(N)-i-1,q) # combinations on the right >= 1
            result[p] += left * right * N[i]
    return result
            
def combProb(N,k):
    Cnk = comb(len(N),k)
    return [S/Cnk for S in countComb(N,k)]

输出：

print(countComb([1,2,3],2)) # [4, 8]
print(combProb([1,2,3],2))  # [1.3333333333333333, 2.6666666666666665]

print(countComb([1,2,3,4,5],3)) # [15, 30, 45]
print(combProb([1,2,3,4,5],3))  # [1.5, 3.0, 4.5]

# test with large number of combinations:

print(countComb(list(range(1,301)),7))
[1521500803497675, 3043001606995350, 4564502410493025, 
 6086003213990700, 7607504017488375, 9129004820986050,
 10650505624483725]

print(combProb(list(range(1,301)),7))
[37.625, 75.25, 112.875, 150.5, 188.125, 225.75, 263.375]

计算所有排序数组组合的平均值

Calculate average value of all sorted array combinations

python

math

statistics

combinations

combinatorics