Optimizing permutation generator where total of each permutation totals to same value

user_8109057 0
Viewed 80

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.

  1. Sample Size: The number of items in each permutation
  2. Desired Sum: The total that each permutation should add up to
  3. 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:

  1. Can someone help me convert my solution into an iterator?
  2. Is it possible to have a calculation to know the total number of items without seeing the full list?
permutation optimization algorithm python
1 Answers

Here is one way to break this down into two subproblems:

  1. Find all restricted integer partitions of target_sum into sample_size summands s.t. all summands come from set_of_number.
  2. 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.

user_45859630
Related