如何计算组合数？

Question

我有问题,我想计算满足以下条件的组合数:

 a < b < a+d < c < b+d

a, b, c列表的元素在哪里,并且d是固定的增量.

这是一个香草实现:

def count(l, d):
    s = 0
    for a in l:
        for b in l:
            for c in l:
                if a < b < a + d < c < b + d:
                    s += 1
    return s

这是一个测试:

def testCount():
    l = [0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 5, 7, 7, 8, 9, 9, 10, 10]
    assert(32 == count(l, 4)) # Gone through everything by hand.

题

我怎样才能加快速度呢？我正在查看200万的列表大小.

补充资料

我正在处理[-pi,pi]范围内的浮点数.例如,这个限制a < 0.

到目前为止我所拥有的:

我有一些实现,我建立了我用于b和的索引c.但是,以下代码在某些情况下失败.(即这是错误的).

def count(l, d=pi):
    low = lower(l, d)
    high = upper(l, d)
    s = 0
    for indA in range(len(l)):
            for indB in range(indA+1, low[indA]+1):
                    s += low[indB] + 1 - high[indA]
    return s

def lower(l, d=pi):
    '''Returns ind, s.t l[ind[i]] < l[i] + d and l[ind[i]+1] >= l[i] + d, for all i
    Input must be sorted!
    '''
    ind = []
    x = 0
    length = len(l)
    for  elem in l:
        while x < length and l[x] < elem + d:
            x += 1
        if l[x-1] < elem + d:
            ind.append(x-1)
        else:
            assert(x == length)
            ind.append(x)
    return ind


def upper(l, d=pi):
    ''' Returns first index where l[i] > l + d'''
    ind = []
    x = 0
    length = len(l)
    for elem in l:
        while x < length and l[x] <= elem + d:
            x += 1
        ind.append(x)
    return ind

原始问题

最初的问题来自众所周知的数学/综合竞赛.比赛要求您不要在网上发布解决方案.但它是从两周前开始的.

我可以用这个函数生成列表:

def points(n):
    x = 1
    y = 1
    for _ in range(n):
        x = (x * 1248) % 32323
        y = (y * 8421) % 30103
        yield atan2(x - 16161, y - 15051)

def C(n):
    angles = points(n)
    angles.sort()
    return count(angles, pi)

Answer 1

有一种方法可以解决您的问题并产生一种O(n log n)算法。让X为一组值。现在让我们修复b. 令A_b为 值集{ x in X: b - d < x < b }并C_b为 值集{ x in X: b < x < b + d }。如果我们能快速找到|{ (x,y) : A_b X C_b | y > x + d }|，我们就解决了问题。

如果我们对 进行排序X，我们可以将A_b和表示C_b为已排序数组的指针，因为它们是连续的。如果我们b以非降序处理候选者，我们就可以使用滑动窗口算法来维护这些集合。事情是这样的：

1. 种类X。让X = { x_1, x_2, ..., x_n }，x_1 <= x_2 <= ... <= x_n。
2. 设置left = i = 1并设置right使得C_b = { x_{i + 1}, ..., x_right }. 放count = 0
3. 迭代i从1到n。(a,b,c)在每次迭代中，我们找出有效三元组的数量b = x_i。为此，请根据需要增加left和 ，right以便A_b = { x_left, ..., x_{i-1} }和C_b = { x_{i + 1}, ..., x_right }仍然成立。在此过程中，您基本上是从虚数集A_b和中添加和删除元素C_b。(a, c)如果您在其中一个集合中删除或添加一个元素，请检查您添加或销毁的c > a + d、afromA_b和cfrom 的对数C_b（这可以通过在另一个集合中进行简单的二分搜索来实现）。相应地更新count以使不变量count = |{ (x,y) : A_b X C_b | y > x + d }|仍然成立。
4. 总结count每次迭代中的值。这是最终结果。

复杂度是O(n log n).

如果你想用这个算法解决欧拉问题，你必须避免浮点问题。我建议使用仅使用整数算术（使用 2D 向量几何）的自定义比较函数按角度对点进行排序。|a-b| < d也可以仅使用整数运算来实现比较。另外，由于您正在进行模运算2*pi，因此您可能必须引入每个角度的三个副本a：a - 2*pi、a和a + 2*pi。b然后，您只需在范围内查找[0, 2*pi)并将结果除以三。

UPDATE OP 在 Python 中实现了这个算法。显然它包含一些错误，但它展示了总体思路：

def count(X, d):
    X.sort()
    count = 0
    s = 0
    length = len(X)
    a_l = 0
    a_r = 1
    c_l = 0
    c_r = 0
    for b in X:
        if X[a_r-1] < b:
            # find boundaries of A s.t. b -d < a < b
            while a_r < length and X[a_r] < b:
                a_r += 1  # This adds an element to A_b. 
                ind = bisect_right(X, X[a_r-1]+d, c_l, c_r)
                if c_l <= ind < c_r:
                    count += (ind - c_l)
            while a_l < length and X[a_l] <= b - d:
                a_l += 1  # This removes an element from A_b
                ind = bisect_right(X, X[a_l-1]+d, c_l, c_r)
                if c_l <= ind < c_r:
                    count -= (c_r - ind)
            # Find boundaries of C s.t. b < c < b + d
            while c_l < length and X[c_l] <= b:
                c_l += 1  # this removes an element from C_b
                ind = bisect_left(X, X[c_l-1]-d, a_l, a_r)
                if a_l <= ind <= a_r:
                    count -= (ind - a_l)
            while c_r  < length and X[c_r] < b + d:
                c_r += 1 # this adds an element to C_b
                ind = bisect_left(X, X[c_r-1]-d, a_l, a_r)
                if a_l <= ind <= a_r:
                    count += (ind - a_l)
            s += count
    return s