CODEWITHSUNDEEP
pythonperformancepermutationcombinatoricscartesian-product
Louis15
Louis15

Reputation: 315

Fastest way to find sub-lists of a fixed length, from a given list of values, whose elements sum equals a defined number

In Python 3.6, suppose that I have a list of numbers L, and that I want to find all possible sub-lists S of a given pre-chosen length |S|, such that:

A trivial solution for this can be found using the Cartesian Product with itertools.product. For example, suppose L is a simple list of all integers between 1 and 10 (inclusive) and |S| is chosen to be 3. Then:

import itertools
L = range(1,11)
N = 8
Slength = 3
result = [list(seq) for seq in itertools.product(L, repeat=Slength) if sum(seq) == N]

However, as larger lists L are chosen, and or larger |S|, the above approach becomes extremely slow. In fact, even for L = range(1,101) with |S|=5 and N=80, the computer almost freezes and it takes approximately an hour to compute the result.

My take is that:

So, my question/challenge is: is there a way I can do this in a more computationally efficient way? Unless we are talking hundreds of Gigabytes, speed to me is more critical than memory, so the challenge focuses more on speed, even if considerations for memory efficiency are a welcome bonus.

Upvotes: 0

Views: 440

Answers (1)

Juan Estevez
Juan Estevez

Reputation: 866

So given an input list and a target length and sum, you want all the permutations of the numbers in the input list such that:

  1. The sum equals the target sum
  2. The length equals the target length

The following code should be faster:

# Input
input_list = range(1,101)

# Targets
target_sum = 15
target_length = 5

# Available numbers
numbers = set(input_list)

# Initialize the stack
stack = [[num] for num in numbers]

result = []

# Loop until we run out of permutations 
while stack:
    # Get a permutation from the stack
    current = stack.pop()

    # If it's too short
    if len(current) < target_length:
        # And the sum is too small
        if sum(current) < target_sum:
            # Then for each available number
            for num in numbers:
                # Append said number and put the resulting permutation back into the stack
                stack.append(current + [num])

    # If it's not too short and the sum equals the target, add to the result!
    elif sum(current) == target_sum:
        result.append(current)

print(len(result))

Upvotes: 1

Related Questions