2

k = 7
n = 30

def f(k,n):
    p = []
    for i in range(n):
        p.append(len(list(itertools.combinations([x for x in range(2**k)],i)))

The problem that the code above works slow and breaks with error for bigger values of variable. I've tried sklearn.cartesian, but got permutationa as a result when needed combination. I know that there is a way to make it work faster with numpy, but I haven't figure out how to implement it yet. Similar question has answer about numpy, but I don't understand how that np.column_stack((np.repeat(a, b.size),np.tile(b, a.size))) should work in my case. As I see now, i will be a number of demenion of the array and will change and I don't fully undertand what to do with this fact.

Boris Verkhovskiy
  • 14,854
  • 11
  • 100
  • 103
Astrik
  • 21
  • 3
  • 5
    You want the _number_ of combinations. To do that, you create an iterator for the combinations, then it into a list, then take the length of the list (when you could just count the iterator). That's one obvious slowdown. But it's not even relevant, because the number of combinations has a [mathematical formula](https://en.wikipedia.org/wiki/Combination#Number_of_k-combinations) — you don't even need the generator. You don't even need to implement it yourself: see [Python Binomial Coefficient](https://stackoverflow.com/questions/26560726/python-binomial-coefficient) – Amadan Feb 05 '20 at 08:00
  • 1
    What kind of break/error do you get? I suspect it has something to do with memory. In such a case a `numpy` approach won't be any better. Creating large arrays is (nearly) as memory intensive as a large list of tuples. The exact breaking point may differ, but for large enough k and n there will be one. – hpaulj Feb 05 '20 at 08:04

3 Answers3

2

Using the formula for the number of combinations, you can do this computation iteratively simply like this:

def f(k, n):
    p = [1]
    f = 1 << k
    for i in range(1, n):
        p.append((p[-1] * f) // i)
        f -= 1
    return p

# For comparison
def f_orig(k, n):
    import itertools
    p = []
    for i in range(n):
        p.append(len(list(itertools.combinations([x for x in range(2 ** k)],i))))
    return p

# Test
k = 4
n = 5
print(f(k, n))
# [1, 16, 120, 560, 1820]
print(f_orig(k, n))
# [1, 16, 120, 560, 1820]

A small benchmark:

k = 5
n = 8
%timeit f(k, n)
# 1.55 µs ± 498 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit f_orig(k, n)
# 528 ms ± 1.15 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

The difference gets bigger as the number increases though, and also this does not require any additional memory.

jdehesa
  • 58,456
  • 7
  • 77
  • 121
  • You can use `math.comb` instead of defining the function yourself. – Boris Verkhovskiy Feb 05 '20 at 15:06
  • 1
    @Boris Yes, the new [`math.comb`](https://docs.python.org/3/library/math.html#math.comb) would probably be faster for one value, but since here we are building a list of combinatorial values, I think this may be faster, as using [`math.comb`](https://docs.python.org/3/library/math.html#math.comb) would "repeat" a lot of the work. However, you may try it out and see what you get (I don't have Python 3.8 to test it). – jdehesa Feb 05 '20 at 15:36
2

The fastest solution is given by @jdehesa which uses multiplicative formula to compute (recursively) the binomial coefficients. Below are couple of other attempts:

from itertools import accumulate
from scipy.special import binom, comb
import math

def f_math_comb(k, n):
    # works with python 3.8
    N = 1 << k  # N = 2**k
    return [math.comb(N, i) for i in range(n)]

def f_scipy_comb(k, n):
    N = 1 << k 
    return [comb(N, i, exact=True) for i in range(n)]

def f_scipy_binom(k, n):
    N = 1 << k 
    return list(map(int, binom(N, range(n))))

def f_itertools_accumulate(k, n):
    N = 1 << k
    p = (N + 1) / np.arange(1, n) - 1
    int_round = lambda x: int(round(x))
    return [1] + list(map(int_round, accumulate(p, mul)))

def f_multip(k, n):
    # jdehesa's solution
    p = [1]
    f = 1 << k
    for i in range(1, n):
        p.append((p[-1] * f) // i)
        f -= 1
    return p

Benchmark:

k = 8
n = 2**k + 1

%timeit f_math_comb(k, n)
3.32 ms ± 45 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit f_scipy_comb(k, n)
3.23 ms ± 75.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit f_scipy_binom(k, n)
189 µs ± 2.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit f_itertools_accumulate(k, n)
1.03 ms ± 12.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit f_multip(k, n)
102 µs ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

One possible improvement is to use the symmetry relation:

enter image description here

Edit: unfortunately scipy's binom doesn't always return exact results because it uses some approximation to compute binomial coefficients for big values of N. Similarly the f_itertools_accumulate, due to rounding issues for big values of N, is not giving exact results.

Andreas K.
  • 9,282
  • 3
  • 40
  • 45
0

I'm guessing your f hits a memory error when k and n get big enough. This variation should get the length without using up (much) memory

In [167]: def f1(k,n): 
     ...:     p = [] 
     ...:     for i in range(n): 
     ...:         g = itertools.combinations([x for x in range(2**k)],i) 
     ...:         cnt = 0 
     ...:         for x in g: cnt += 1 
     ...:         p.append(cnt) 
     ...:     return p

It returns the same count as your f:

In [168]: f1(5,5)                                                                              
Out[168]: [1, 32, 496, 4960, 35960]
In [169]: f(5,5)                                                                               
Out[169]: [1, 32, 496, 4960, 35960]

It is slower though.

In [170]: timeit f1(5,5)                                                                       
3.47 ms ± 14 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [171]: timeit f(5,5)                                                                        
2.72 ms ± 122 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [175]: timeit -r1 -n1 f1(5,5)                                                               
3.66 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [176]: timeit -r1 -n1 f1(6,5)                                                               
61.4 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [177]: timeit -r1 -n1 f1(7,5)                                                               
1.01 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [178]: timeit -r1 -n1 f1(8,5)                                                               
14.6 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

trying to repeat these times for f, I get the killed right away. I should have tried from the other end:

In [179]: timeit -r1 -n1 f(8,5)                                                                
Killed

Anyways, it does show that my counting without accumulating handles larger values than your method, even if it does start out slower.

hpaulj
  • 221,503
  • 14
  • 230
  • 353