# Permutations with a sum constraint

I have made the following function that gives the combinations permuted of n elements with a constrain/rule. This consist on creating a dataframe with all combination of numbers from 0 to n that sums n.

## Function

import pandas as pd
import itertools
import numpy as np

def combinations_permuted(n_elm):
items = list(range(0,n_elm+1,1))
combinations = pd.DataFrame(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.combinations_with_replacement(items, n_elm)))))
comb_permuted = pd.DataFrame()
for index, combination in combinations.iterrows():
comb_permuted=comb_permuted.append(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.permutations(combination.tolist(), n_elm)))))

return(comb_permuted.drop_duplicates().as_matrix())


## Example

array([[0, 0, 3],
[0, 3, 0],
[3, 0, 0],
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
[1, 1, 1]], dtype=int64)


The problem is that is taking a long time when n_elm is "big" for example 9. I think this code can be improving in terms of time performance.

Maybe by replacing the for loop with a map function.

Any help to get it?

• What Python version are you targeting? – Mast Mar 21 '18 at 13:41
• – juvian Mar 21 '18 at 14:32

def combinations_permuted(n_elm):


IMO n (as used in the description of the code in the question) is more readable than n_elm.

    items = list(range(0,n_elm+1,1))


1 is the default step, and range isn't so obscure a function that the maintenance programmer would wonder what range(0, n+1) does.

    combinations = pd.DataFrame(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.combinations_with_replacement(items, n_elm)))))
comb_permuted = pd.DataFrame()
for index, combination in combinations.iterrows():
comb_permuted=comb_permuted.append(list(filter(lambda x: np.sum(x)==n_elm,list(itertools.permutations(combination.tolist(), n_elm)))))

return(comb_permuted.drop_duplicates().as_matrix())


There are two things here which sound warning bells:

1. comb_permuted=comb_permuted.append. The documentation for DataFrame.append says

Iteratively appending rows to a DataFrame can be more computationally intensive than a single concatenate. A better solution is to append those rows to a list and then concatenate the list with the original DataFrame all at once.

2. drop_duplicates(). That says that the generation process is doing more work that it needs to.

A KISS approach would be to replace the combinations_with_replacement, permutations, drop_duplicates chain with itertools.product. This is much faster at n = 3, but already slower at n = 5 (because it's still doing more work that it needs to, and filtering).

The efficient approach is to do only the work that's necessary. A quick and dirty implementation (i.e. please tidy it up before using) calculates for n = 6 in less time than it takes the original code to calculate n = 3:

def combinations_recursive_inner(n, buf, gaps, sum, accum):
if gaps == 0:
accum.append(list(buf))
else:
for x in range(0, n+1):
if sum + x + (gaps - 1) * n < n: continue
if sum + x > n: break
combinations_recursive_inner(n, buf + [x], gaps - 1, sum + x, accum)

def combinations_recursive(n):
accum = []
combinations_recursive_inner(n, [], n, 0, accum)
return pd.DataFrame(accum).as_matrix()


Online test and benchmark