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

Question

Say I have 4 ranges: 1..10, 1..20, 1..30, 1..40.

How do I calculate the number of unique (i.e. same numbers occur same number of times) 4-combinations for the 4 ranges? Something like this, but more efficient:

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)

Also I need to calculate the number of such combinations having 2 pairs of identical numbers, e.g. (1, 1, 1, 1), (1, 1, 2, 2), etc.

Your question is confusing, so I can't tell if this is a duplicate. Just what do you mean by "unique"? Are `(1,1,1,2)` and `(1,1,2,1)` distinct? What about `(1,1,1,2)` and `(1,1,2,2,)`? Your sample code treats all the 4-tuples as distinct, so you will get `cnt=10*20*30*40`. And your second question at the end makes things more confusing. — Rory Daulton, May 21 '16 at 22:43
https://en.wikipedia.org/wiki/Permutation gives an equation as n!/(n-k)! and https://en.wikipedia.org/wiki/Combination gives an equation as n!/(k!(n-k)!) which, if this is what are after, would be simpler than any loops. — chase, May 21 '16 at 22:52
@Rory `(1,1,1,2)` and `(1,1,2,1)` are not distinct. The sample above **doesn't** produce `cnt=10*20*30*40` (which you can see yourself if you run it). — planetp, May 21 '16 at 22:59
Oops, you are right about the value of `cnt`: my mistake. The answer by chase is correct if the four ranges are identical, which they are not in your problem so that complicates things. So, are we correct in saying that your question is actually a math problem rather than a computing problem? — Rory Daulton, May 21 '16 at 23:03
A paraphrase of the question, from its code implementation, is "which is the number of all *sorted* tuples, with elements extracted from different intervals, taking into account as sorted also the tuples with repeated elements?" — gboffi, May 21 '16 at 23:43
@gboffi I need two numbers: the number of 'unique sorted tuples, with elements extracted from different intervals', **and** the number of those that have 2 pairs. Actually, [@Mark Tolonen](http://stackoverflow.com/a/37368748/275088) posted a working solution, but it has the same problem as mine: it's too slow for bigger ranges. I need to calculate the result mathematically, rather then enumerating all possible tuples. — planetp, May 21 '16 at 23:53
Have you considered asking your question on the math SE site? Should you ask _there_ could you please post _here_, in the form of a comment, a link to the math SE question, as I'm interested in the outcome of your problem? Thank you in advance, ciao. — gboffi, May 22 '16 at 09:35
Another suggestion, you could incorporate my explanation in your question that, as it is now and judging from the content of different comments, could be a little misleading, ... and an edit has the added benefit or taking your Q to the top of SO main page — gboffi, May 22 '16 at 09:46

Mark Tolonen · Answer 1 · 2016-05-21T23:19:35.413

0

If you want unique combinations (only counting [1,1,1,2] and [2,1,1,1] once), it can be brute forced with:

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

Counting the ones that have 2 pairs of identical numbers:

>>> 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

edited May 21 '16 at 23:19

answered May 21 '16 at 22:49

Mark Tolonen

166,664
26
169
251

This is basically the same algo as in the OP, just using the `itertools` functions. What I need is something that will work when ranges become hundreds. – planetp May 21 '16 at 23:33
@planetp, it answers the question as asked, and it *is* more efficient (<1s). Maybe you should fix your question to be more specific, including your worst case scenario. – Mark Tolonen May 22 '16 at 00:56

score 0 · Answer 2 · answered May 22 '16 at 10:19

Your second question is easy, because the number of tuples (i, i, j, j), i<=j is of course equal to the number of tuples (i, j), i<=j.

From your question, it seems that you deal with intervals that share the origin and are strictly larger than the preceding ones, let's write a tuple as (i1, i2, j3, j4) with the understanding that i1 comes from range r1 etc. At this point we know that our outcome is determined only by ranges r1 and r3.

As an illustration, consider r1 = range(4) and r3 = range(8) and represent the cartesian product of i1 and j3 in a matrix, which are the good elements?

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

I have separated the good from the bad and the number of good elements is 4×8-(4-1)² — the answer N2 to your second question, if I'm guessing correctly the constraints that you have implicitly posed, is

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

I'm confident that, from this solution, it is possible to derive an answer to your 1st question but I leave this more difficult part to a better answer.

Paul Hankin · Accepted Answer · 2016-05-22T12:06:23.560

You can optimize this from the inside out to compute the result.

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)

The inner loop is simple: for l in range(k, 40) adds one to cnt 40-k times. Note: it's not quite clear whether you intend ranges to be inclusive or not; in Python they don't include their end point, but 1..10 suggests you intend them to be inclusive.

Taking an extra loop, we have sum(40-k for k in range(j, 30)). It's feasible to compute this (using sum(1+2+3...+n) = n(n+1)/2), but it quickly becomes messy. Instead, we can cheat and use Wolfram Alpha or similar to compute that it's (j^2 - 81j + 1530)/2.

Adding in another loop: sum((j^2 - 81j + 1530)/2 for j in range(i, 20)). Again, we could solve this using the additional formula of sums of squares of a range of numbers, but we can cheat again to get: 8075 - (i-1)(i^2 - 122i + 5490)/6.

With the final loop included, we get 49725.

That was for fixed ranges, but the same idea works for arbitrary ranges. For this program:

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)

we can use Wolfram Alpha to compute 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) to get this beast:

Again, in principle we could have computed this by hand, but it's difficult to do so without making an error.

For the second part of the question: sums consisting of two pairs, one can use the same technique. There's fewer sums because "two pairs" means j==i and l==k, so one gets the equivalent of this Python program:

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

That's sum(sum(1 for k=i to n2) for i=1 to n1) which comes out to -n1(n1 - 2*n2 - 1)/2.

Nice. Any idea how to mathematically calculate the 2nd number? (i.e. the number of combinations containing two pairs) — planetp, May 22 '16 at 11:38
Yes (if I understand the question) -- you can use the same technique with j=i and l=j you just get fewer sums -- sum(sum(1 for k=i to n3) for i=1 to n1). — Paul Hankin, May 22 '16 at 12:02

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

3 Answers3