Number of combinations (from n to k) is there a fast algorithm? Python
The number of combinations can be found using recursion and, accordingly, the recurrence relation. The code turns out like this:
def C(n, k):
if k == n or k == 0:
return 1
if k != 1:
return C(n-1, k) + C(n-1, k-1)
else:
return n
print(C(int(input()), int(input())))
But I know that recursion is not fast and not always reliable. Are there any other algorithms and how fast are they?
3 answers
Through the factorial is slow and not efficient.
In the formula n! / (k! (n - k)!), if you reduce it, you get (n-k+1)(n-k+2)..n/k!
The following code is obtained:
def С(n, k):
if 0 <= k <= n:
nn = 1
kk = 1
for t in xrange(1, min(k, n - k) + 1):
nn *= n
kk *= t
n -= 1
return nn // kk
else:
return 0
You can also view the library itertools:
combinations('ABCD', 2) # AB AC AD BC BD CD
I suggest using the module itertools, where the necessary operation is immediately implemented. It makes the necessary combinations. It will not be difficult to count their number.
import itertools
def C(n, k):
return len(list(itertools.combinations(range(1, n), k)))
I want to note that it can make combinations of anything (i.e. you can pass any iterable container).
For the vehicle, it is no longer relevant, probably, but it can be useful to someone.
Pascal's triangle (combinations are binomial coefficients).
To "draw" it, you don't need to multiply it at all.
It can't be any faster.