setting a condition inside a for loop

Question

below for loop for creating all possible combinations of weights for 15 varuabel, however, i only need the combination where the total variables = 1, but, the loop is so huge that it ran for 11 hours and still not yet finished so the code can execute the lines after the loop and get me the combinations where the sum = 1, is there a way where i can set my condition inside the loop ?

import pandas as pd, numpy, itertools


w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15 = (
  list(
    numpy.arange(0, 11, 1)/10
  ) for i in range(15)
)
comb_list = [w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15]
weights_df = pd.DataFrame(
  columns = ['w1', 'w2', 'w3', 'w4', 'w5', 'w6', 'w7', 'w8', 'w9', 'w10', 'w11', 'w12', 'w13', 'w14', 'w15']
)

for weights in itertools.product(*comb_list):
    weights_df.loc[len(weights_df)] = weights


weights_df.loc[:,'total_weight'] = (weights_df['w1'] 
  + weights_df['w2'] + weights_df['w3'] 
  + weights_df['w4'] + weights_df['w5']
  + weights_df['w6'] + weights_df['w7']
  + weights_df['w8'] + weights_df['w9'] 
  + weights_df['10'] + weights_df['w11']
  + weights_df['w12'] + weights_df['w13']
  + weights_df['w14'] + weights_df['w15'])
weights_df = weights_df[weights_df['total_weight'] == 1]

Answer 1

Claim

This problem can be solved in less than 25 seconds rather than 11 hours as follows.

1. Use Backtracking to search the space of F11^15 or 4 quintillion search space
2. Backtracking provides a mechanism discarding parts of the search space that don't satisfy the constraint (i.e. the sum of weights constraint)

Code

class BackTrack:
  max_n = 15      # Max number of weights (i.e. 15)
  max_sum = 10    # sum of integer weights
  normalization = 0.1  # factor to multiply integer weights to make them between 0 and 1

  def solve(self, sum_ = 0, weights = [], solutions = []):
    """Find weights that sum to 1 by finding weights that sum to 10 then multiply by 0.1
       Integer weights are used during backtracking to avoid issues of rounding errors in computations"""
    if len(weights) > BackTrack.max_n or sum_ > BackTrack.max_sum:
      # Backtrack since no solution since either
      # too many weights or sum of current weights is too large
      return

    if len(weights) == BackTrack.max_n and sum_ == BackTrack.max_sum:
      # Found solution
      # Add weights normalized to range 0 to 1 by multiplyfing by
      # normalization constant
      solutions.append([weight*BackTrack.normalization for weight in weights])
      return solutions

    # Add additional weights
    for weight in range(BackTrack.max_sum + 1):
      if weight + sum_ > BackTrack.max_sum:
        # No more solutions for this or higher weight
        break
      else:
        # Recursively find solutions for this weight
        self.solve(sum_ + weight, weights + [weight], solutions)

    return solutions

Test

# start timer
import time
t0 = time.time()  

# Solve for weigt combinations
b = BackTrack()
weights = b.solve(0, [], [])

# Show results
print('Elapsed Time {:.2f} seconds'.format(time.time() - t0))
print("Number of Solutions: {:,}".format(len(weights)))
print('Head of Solutions (first 4): ', *weights[:5], sep = '\n')
print('Tail of Solutions (last 4): ', *weights[-5:], sep = '\n')

Output

Elapsed Time 23.78 seconds
Number of Solutions: 1,961,256
Head of Solutions (first 4): 
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.9]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.2, 0.8]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.30000000000000004, 0.7000000000000001]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.4, 0.6000000000000001]
Tail of Solutions (last 4): 
[0.9, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.9, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

Generator Version

In case we create a generator for the weights which removes the necessity of storing all 1.9M weight vectors as follows.

class BackTrack:
  max_n = 15      # Max number of weights (i.e. 15)
  max_sum = 10    # sum of integer weights
  normalization = 0.1  # factor to multiply integer weights to make them between 0 and 1

  def solve(self, sum_ = 0, weights = []):
    """Find weights that sum to 1 by finding weights that sum to 10 then multiply by 0.1
       Integer weights are used during backtracking to avoid issues of rounding errors in computations"""
    if len(weights) > BackTrack.max_n or sum_ > BackTrack.max_sum:
      # No solution since too many weights or sum is too large
      return

    if len(weights) == BackTrack.max_n and sum_ == BackTrack.max_sum:
      # Add path normalized to range 0 to 1 by multiplyfing by
      # normalization constant
      yield [weight*BackTrack.normalization for weight in weights]

    # Check for new solutions
    for weight in range(BackTrack.max_sum + 1):
      if weight + sum_ > BackTrack.max_sum:
        # No more solutions for this or higher weight
        break
      else:
        # Recursively find solutions for this weight
        yield from self.solve(sum_ + weight, weights + [weight])

Usage

b = BackTrack()
for weights in b.solve(0, []):
    do_something(weights) # current w1, w2, ... w15

Answer 2

There are fifteen lists, each with eleven (0-10 inclusive) elements. You're taking the Cartesian product of all of those.

That's 11^15 items you're iterating over. About 4 quintillion.

Sure, you could move your test inside your for-loop, but I don't think that's going to be enough to make this script practical.

You could also break your loop into a 15x nested loop with a filter at each level; I would expect that to give you an order-of-magnitude improvement in runtime. But I don't think it will be enough.

You need to go back and consider the problem abstractly, and figure out some less-brute-force way of calculating whatever it is you're trying to calculate.