Get a number of possible combinations Python

Question

How do I get a number of the possible combinations knowing the number of characters used in generating the combinations and a range of lengths.

To get all permutations i would use:

chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
minLen = 1
maxLen = 3

total = 0
for i in range(minLen,maxLen+1):
    total += len(chars)**i

How would I do this for combinations? When repetition is not allowed.

I'm sure there's a mathematical formula to do this but I couldn't find it anywhere.

Thanks!

EDIT:
I realised that code might not be readable so here's an explenation:

It's pretty obvious what the variables are: minimum combination length, maximum, used characters...

The for loop goes from 1 to 3 and each time it adds this to the total: length of characters (len(chars)) to the power of i (the current iteration's length).

This is a basic way of calculating permutations.

I'm probably completely underestimating what you're trying to do here- but are you thinking of the number of [k-combinations] (https://en.wikipedia.org/wiki/Combination). If so, this question is probably a duplicate. Best. — Tom, Nov 27 '15 at 14:08
I am. I'm not sure on how to implement this programmatically (so I'm asking here) :) — Ciprum, Nov 27 '15 at 14:11
[itertools permutations](https://docs.python.org/2/library/itertools.html#itertools.permutations) would seem to be your friend here. — SiHa, Nov 27 '15 at 14:12
You could do it just with nested for loops. In your example you can just have 3 nested for loops and brute force it. — Ogen, Nov 27 '15 at 14:13
I am working with hundreds of thousands of numbers. I don't think brute-forcing is a good idea. — Ciprum, Nov 27 '15 at 14:15
@Tom You can flag it if you want, but none of the answers answer my question correctly. They are either too slow (such as len(list(itertools.combinations()))) or don't work as expected. — Ciprum, Nov 27 '15 at 14:18
Thanks for your patience, but consider if you just want the number of combinations used the closed form solution from the answer linked to, rather than generating them all and counting the length. — Tom, Nov 27 '15 at 14:23

score 2 · Accepted Answer · answered Nov 27 '15 at 14:56

2

So, you actually need a way to count the Binomial coefficient, right?

import math

def binomial_cooefficient(n: int, k: int) -> int:
    n_fac = math.factorial(n)
    k_fac = math.factorial(k)
    n_minus_k_fac = math.factorial(n - k)
    return n_fac/(k_fac*n_minus_k_fac)

This might not be the most optimal implementation, but it works :)

answered Nov 27 '15 at 14:56

Maciek

3,174
1
22
26

Thanks! Exactly what I needed. – Ciprum Nov 27 '15 at 16:31
For anyone who reaches this answer, there is a `math.comb` function now to calculate the binomial coefficient (n choose k). – takanuva15 Aug 05 '22 at 12:51

Imanol Luengo · Answer 2 · 2015-11-27T15:29:40.400

I believe that you are looking for scipy.misc.comb (which gives you the number of unique combinations of a binomial (of the form of from N take X):

>>> from scipy.misc import comb
>>> comb(10, 1) # Num of unique combinations of *from 10 take 1*
10.0
>>> comb(10, 2) # Num of unique combinations of *from 10 take 2*
45.0

And so on.. You can then get a nice reduce:

>>> total_len = 10
>>> min_size = 1
>>> max_size = 2
>>> reduce(lambda acc, x: acc + comb(total_len, x), range(min_size, max_size+1), 0)
55.0

The above reduce is the 1-liner functional equivalent of your for:

>>> total = 0
    for x in range(min_size, max_size+1):
        total += comb(total_len, x)

As a side note, if you use comb(total_len, x, exact=True) you will get the result as an integer rather than a float.

Get a number of possible combinations Python

2 Answers2