Reputation: 315
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:
S
has to have length smaller than L
, that is |S| < |L|
S
can only contain numbers present in L
S
do not have to be unique (they can appear repeatedly)S
should be equal to a pre-determined number N
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:
N
itertools.product
to just keep much much fewerSo, 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
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:
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