I’m wanting to create a list of permutations or cartesian products (not sure which one applies here) where the sum of values in each permutation totals to a provided value.
There should be three parameters required for the function.
- Sample Size: The number of items in each permutation
- Desired Sum: The total that each permutation should add up to
- Set of Numbers: The set of numbers that can be included with repetition in the permutations
I have an implementation working below but it seems quite slow I would prefer to use an iterator to stream the results but I would also need a function that would be able to calculate the total number of items that the iterator would produce.
def buildPerms(sample_size, desired_sum, set_of_number): blank = [0] * sample_size return recurseBuildPerms([], blank, set_of_number, desired_sum) def recurseBuildPerms(perms, blank, values, desired_size, search_index = 0): for i in range(0, len(values)): for j in range(search_index, len(blank)): if(blank[j] == 0): new_blank = blank.copy() new_blank[j] = values[i] remainder = desired_size - sum(new_blank) new_values = list(filter(lambda x: x <= remainder, values)) if(len(new_values) > 0): recurseBuildPerms(perms, new_blank, new_values, desired_size, j) elif(sum(new_blank) <= desired_size): perms.append( new_blank) return perms perms = buildPerms(4, 10, [1,2,3]) print(perms) ## Output [[1, 3, 3, 3], [2, 2, 3, 3], [2, 3, 2, 3], [2, 3, 3, 2], [3, 1, 3, 3], [3, 2, 2, 3], [3, 2, 3, 2], [3, 3, 1, 3], [3, 3, 2, 2], [3, 3, 3, 1]]
https://www.online-python.com/9cmOev3zlg
Questions:
- Can someone help me convert my solution into an iterator?
- Is it possible to have a calculation to know the total number of items without seeing the full list?
Advertisement
Answer
Here is one way to break this down into two subproblems:
- Find all restricted integer partitions of
target_sum
intosample_size
summands s.t. all summands come fromset_of_number
. - Compute multiset permutations for each partition (takes up most of the time).
Problem 1 can be solved with dynamic programming. I used multiset_permutations
from sympy
for part 2, although you might be able to get better performance by writing your own numba code.
Here is the code:
from functools import lru_cache from sympy.utilities.iterables import multiset_permutations @lru_cache(None) def restricted_partitions(n, k, *xs): 'partitions of n into k summands using only elements in xs (assumed positive integers)' if n == k == 0: # case of unique empty partition return [[]] elif n <= 0 or k <= 0 or not xs: # case where no partition is possible return [] # general case result = list() x = xs[0] # element x we consider including in a partition i = 0 # number of times x should be included while True: i += 1 if i > k or x * i > n: break for rest in restricted_partitions(n - x * i, k - i, *xs[1:]): result.append([x] * i + rest) result.extend(restricted_partitions(n, k, *xs[1:])) return result def buildPerms2(sample_size, desired_sum, set_of_number): for part in restricted_partitions(desired_sum, sample_size, *set_of_number): yield from multiset_permutations(part) # %timeit sum(1 for _ in buildPerms2(8, 16, [1, 2, 3, 4])) # 16 ms # %timeit sum(1 for _ in buildPerms (8, 16, [1, 2, 3, 4])) # 604 ms
The current solution requires computing all restricted partitions before iteration can begin, but it may still be practical if restricted partitions can be computed quickly. It may be possible to compute partitions iteratively as well, although this may require more work.
On the second question, you can indeed count the number of such permutations without generating them all:
# present in the builtin math library for Python 3.8+ @lru_cache(None) def binomial(n, k): if k == 0: return 1 if n == 0: return 0 return binomial(n - 1, k) + binomial(n - 1, k - 1) @lru_cache(None) def perm_counts(n, k, *xs): if n == k == 0: # case of unique empty partition return 1 elif n <= 0 or k <= 0 or not xs: # case where no partition is possible return 0 # general case result = 0 x = xs[0] # element x we consider including in a partition i = 0 # number of times x should be included while True: i += 1 if i > k or x * i > n: break result += binomial(k, i) * perm_counts(n - x * i, k - i, *xs[1:]) result += perm_counts(n, k, *xs[1:]) return result # assert perm_counts(15, 6, *[1,2,3,4]) == sum(1 for _ in buildPerms2(6, 15, [1,2,3,4])) == 580 # perm_counts(1000, 100, *[1,2,4,8,16,32,64]) # 902366143258890463230784240045750280765827746908124462169947051257879292738672
The function used to count all restricted permutations looks very similar to the function that generates partitions above. The only significant change is in the following line:
result += binomial(k, i) * perm_counts(n - x * i, k - i, *xs[1:])
There are i
copies of x
to include and k
possible positions where x
‘s may end up. To account for this multiplicity, the number of ways to resolve the recursive sub-problem is multiplied by k
choose i
.