符合某些标准的计数组合？

Question

我正在使用一个大约700个观测值的数据集，并希望计算4个观测值的多少个组合的平均值介于高值和低值之间

我已经创建了可以做到这一点的代码，但是将其应用到我的更大的数据集会导致数十亿个组合，并且需要几天时间才能运行。当然，有一种更快或更有效的方法可以做到这一点

以下是我尝试过的：

import pandas as pd
import numpy as np
import itertools
from numpy import mean


df = pd.DataFrame(np.random.randint(0,100,size=(700, 2)), columns=['Value', 'Other'])

truehi = 25
truelow = 10

combs = sum(1 for e in itertools.combinations(df['Value'], 4))

meets = 0
for item in itertools.combinations(df['Value'], 4):
    avg = mean(item)
    if (avg <= truehi) & (avg >= truelow):
        meets = meets + 1

我发现这个问题看起来应该满足我的需要，但我很难适应我的具体情况。如果有人能帮忙，那将是难以置信的：Efficiently count sets in a cartesian product that sum above a specific number

Answer 1

这里一个有用的想法是itertools.combinations返回组合 按字典顺序。因此，如果对输入序列进行排序，则输出 序列也将被排序

这有助于减少要评估的组合顺序，因为 确定如果item[0] > truehi，那么item[0] >= item[1] >= item[2] >= item[3]，那么没有更多的组合 将符合条件

这允许我们更早地停止循环。对于我运行的一些测试，它跳过了 尺寸为100的最后30%左右的组合，基于以下试验数据： 高斯分布

为了进一步扩展这个想法，我编写了combinations的自定义版本 对于1级和2级使用相同的方法。这又减少了40%左右

提高运行时性能的其他一些想法是计算 使用对数版本的n take 4而不是迭代的组合 在所有组合中（由注释@Crisal暗示）， 并使用np.sum，而不是np.avg（comment@Sam cd）

对于尺寸100，这将我的机器上的运行时间从42秒减少到7.5秒

对于大小200，我使用下面的算法测量217s运行时，而不是 评估69.3%的组合。这大约是29倍长， 尽管整体组合的数量只有16.5倍左右 更大

尺寸为300时，运行时间约为514s，在一个示例中，它跳过了 85%的组合

对于大小700，运行时大约为21858s，在一个示例中，它跳过了 79%的组合

import math
import pandas as pd
import numpy as np

setsz = 200 #100 #700 is target, too many combinations
df = pd.DataFrame(np.random.randint(0, 100, size=(setsz, 2)),
                  columns=['Value', 'Other'])
truehi = 25
truelow = 10
# With combinations, this is a factiorials game:
# combs has n! / ((n-4)! * 4!) combinations;
# about 10**10 for n=700
# n=100 is 3_921_225; lapse of 42.3s; sample 159_004 meets
# combs = sum(1 for e in itertools.combinations(df['Value'], 4))
log_fact_n = math.log(math.factorial(setsz), 10)
log_fact_n_4 = math.log(math.factorial(setsz-4), 10)
log_fact_4 = math.log(math.factorial(4), 10)
log_combs = log_fact_n - log_fact_n_4 - log_fact_4
meets = 0

def c_combinations(iterable, r, vmax):
    # Modified from itertools.combinations
    # combinations('ABCD', 2)  > AB AC AD BC BD CD
    # combinations(range(4), 3)  > 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n or r < 4:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        if pool[indices[0]] > vmax:
            return
        sum_pool_01 = pool[indices[0]] + pool[indices[1]]
        if sum_pool_01 > 2*vmax:
            for i in reversed(range(1, r)):
                indices[i] = i + n - r
            continue
        if sum_pool_01 + pool[indices[2]] > 3*vmax:
            for i in reversed(range(2, r)):
                indices[i] = i + n - r
            continue
        yield tuple(pool[i] for i in indices)

first = None
for i,item in enumerate(c_combinations(sorted(df['Value']), 4, truehi)):
    sum = np.sum(item)
    if 4*truelow <= sum <= 4*truehi:
        if first is None:
            first = i
        meets = meets + 1
    if item[0] > truehi:
        break
print(f"{meets:,} found in 10**{log_combs:,.6} combinations")
print(f"First match {first:,}, last iteration {i:,}")
# 5,711,643 found in 10**7.8108 combinations
# First match 87, last iteration 19,889,389

还有一件事需要考虑：对于非常大的数据集，估计数量 也可以通过使用采样来进行满足特定条件的组合的测试 技术。当你可以第一次选择时，为什么要运行数十亿个组合 一个随机的子集和数百万个组合