Optimize generator for multivariate polynomial exponents

HI, I'm try to find a general expression to obtain exponents of a multivariate polynomial of order order and with n_variables, like the one presented in this reference in equation (3).

Here is my current code, which uses an itertools.product generator.

def generalized_taylor_expansion_exponents( order, n_variables ):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    exps = (p for p in itertools.product(range(order+1)开发者_运维问答, repeat=n_variables) if sum(p) <= order)
    # discard the first element, which is all zeros..
    exps.next()
    return exps

The desired out is this:

for i in generalized_taylor_expansion_exponents(order=3, n_variables=3): 
    print i

(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 1, 0)
(0, 1, 1)
(0, 1, 2)
(0, 2, 0)
(0, 2, 1)
(0, 3, 0)
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(1, 1, 0)
(1, 1, 1)
(1, 2, 0)
(2, 0, 0)
(2, 0, 1)
(2, 1, 0)
(3, 0, 0)

Actually this code executes fast, because the generator object is only created. If i want to fill a list with values from this generator execution really starts to be slow, mainly because of the high number of calls to sum. Tipical value for order and n_variables is 5 and 10, respectively.

How can i significantly improve execution speed?

Thanks for any help.

Davide Lasagna

---

Actually your biggest performance issue is that most of the tuples you're generating are too big and need to be thrown away. The following should generate exactly the tuples you want.

def generalized_taylor_expansion_exponents( order, n_variables ):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    pattern = [0] * n_variables
    for current_sum in range(1, order+1):
        pattern[0] = current_sum
        yield tuple(pattern)
        while pattern[-1] < current_sum:
            for i in range(2, n_variables + 1):
                if 0 < pattern[n_variables - i]:
                    pattern[n_variables - i] -= 1
                    if 2 < i:
                        pattern[n_variables - i + 1] = 1 + pattern[-1]
                        pattern[-1] = 0
                    else:
                        pattern[-1] += 1
                    break
            yield tuple(pattern)
        pattern[-1] = 0

---

I would try writing it recursively so as to generate only the desired elements:

def _gtee_helper(order, n_variables):
    if n_variables == 0:
        yield ()
        return
    for i in range(order + 1):
        for result in _gtee_helper(order - i, n_variables - 1):
            yield (i,) + result


def generalized_taylor_expansion_exponents(order, n_variables):
    """
    Find the exponents of a multivariate polynomial expression of order
    `order` and `n_variable` number of variables. 
    """
    result = _gtee_helper(order, n_variables)
    result.next() # discard the first element, which is all zeros
    return result