如何计算 4 个不同范围的唯一 4 种组合的数量？

Question

假设我有 4 个范围：1..10、1..20、1..30、1..40。

如何计算 4 个范围的唯一（即相同数字出现相同次数）4 种组合的数量？像这样，但效率更高：

cnt = 0
for i in range(1, 10):
    for j in range(i, 20):
        for k in range(j, 30):
            for l in range(k, 40):
                cnt += 1
print(cnt)

我还需要计算具有 2 对相同数字的此类组合的数量，例如(1, 1, 1, 1)、(1, 1, 2, 2) 等

Answer 1

如果你想要独特的组合（只计算 [1,1,1,2] 和 [2,1,1,1] 一次），它可以被暴力破解：

>>> from itertools import product
>>> len(set(tuple(sorted(x)) for x in product(range(10),range(20),range(30),range(40))))
58565

计算有 2 对相同数字的数：

>>> L=set(tuple(sorted(x)) for x in product(range(10),range(20),range(30),range(40)))
>>> sum(a==b and c==d for a,b,c,d in L) # Leveraging True(1) and False(0)
255

Answer 2

你的第二个问题很简单，因为元组数(i, i, j, j), i<=j当然等于元组数(i, j), i<=j.

从你的问题来看，你似乎处理的区间共享原点并且严格大于前面的区间，让我们将元组写成 (i1, i2, j3, j4) 并理解 i1 来自范围 r1 等。此时我们知道我们的结果仅由范围 r1 和 r3.

决定

作为示例，考虑r1 = range(4)和r3 = range(8)并在矩阵中表示i1和j3的笛卡尔积，即好个元素?

00 01 02 03 04 05 06 07
   11 12 13 14 15 16 17
10    22 23 24 25 26 27
20 21    33 34 35 36 37
30 31 32

我已经把好的和坏的分开了，好的元素的数量是 4×8-(4-1)² — 你第二个问题的答案 N2，如果我猜测正确地，你隐式提出的约束是

                       N2 = len(r1)*len(r3) - (len(r1)-1)**2

我相信，从这个解决方案中，可以得出您第一个问题的答案，但我将这个更困难的部分留给更好的答案。

Answer 3

您可以从内到外对其进行优化以计算结果。

cnt = 0
for i in range(1, 10):
    for j in range(i, 20):
        for k in range(j, 30):
            for l in range(k, 40):
                cnt += 1
print(cnt)

内部循环很简单：for l in range(k, 40) 加一到 cnt 40-k 次。注意：尚不清楚您是否打算包含范围；在 Python 中，它们不包括它们的终点，但 1..10 建议您希望它们具有包容性。

再进行一次循环，我们有 sum(40-k for k in range(j, 30))。计算这个是可行的（使用 sum(1+2+3...+n) = n(n+1)/2），但很快就会变得混乱。相反，我们可以作弊并使用 Wolfram Alpha 或类似的方法来计算它是 (j^2 - 81j + 1530)/2.

添加另一个循环：sum((j^2 - 81j + 1530)/2 for j in range(i, 20))。同样，我们可以使用一系列数字的平方和的附加公式来解决这个问题，但我们可以 cheat again 得到：8075 - (i-1)(i^2 - 122i + 5490)/6.

包括最后一个循环，we get 49725.

那是针对固定范围的，但同样的想法适用于任意范围。对于此程序：

cnt = 0
for i in range(1, n1+1):
    for j in range(i, n2+1):
        for k in range(j, n3+1):
            for l in range(k, n4+1):
                cnt += 1
print(cnt)

我们可以使用 Wolfram Alpha 来计算 sum(sum(sum(sum(1 for l=k to n4) for k=j to n3) for j=i to n2) for i=1 to n1) 得到这个野兽：

同样，原则上我们可以手动计算，但很难做到不出错。

对于问题的第二部分：由两对组成的和，可以使用相同的技术。总和较少，因为 "two pairs" 表示 j==i 和 l==k，因此可以得到与此 Python 程序等效的内容：

cnt = 0
for i in range(1, n1+1):
    j = i
    for k in range(j, n2+1):
        l = k
        cnt += 1

那是 sum(sum(1 for k=i to n2) for i=1 to n1) 结果是 -n1(n1 - 2*n2 - 1)/2。

如何计算 4 个不同范围的唯一 4 种组合的数量？

How to calculate the number of unique 4-combinations for 4 different ranges?

python

combinations