установка условия внутри цикла for

Question

ниже для l oop для создания всех возможных комбинаций весов для 15 переменных. Однако мне нужна только комбинация, где суммарные переменные = 1, но l oop настолько велика, что она работает в течение 11 часов. и все еще не закончено, поэтому код может выполнить строки после l oop и получить мне комбинации, где сумма = 1, есть ли способ, где я могу установить свое условие внутри l oop?

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

Существует пятнадцать списков, каждый из которых содержит одиннадцать (0-10 включительно) элементов. Вы берете декартово произведение всех этих.

Это 11 ^ 15 пунктов, которые вы просматриваете. Около 4 квинтиллионов.

Конечно, вы можете перенести свой тест внутрь своего for-l oop, но я не думаю, что этого будет достаточно, чтобы сделать этот сценарий практичным.

Вы также можете разбить свой l oop на вложенный в 15x l oop с фильтром на каждом уровне; Я ожидаю, что это даст вам улучшение на порядок во время выполнения. Но я не думаю, что этого будет достаточно.

Вам необходимо go вернуться назад и рассмотреть проблему абстрактно, а также придумать какой-то менее грубый способ расчета того, что вы пытаетесь вычислить.

Answer 2

Заявка

Эту проблему можно решить менее чем за 25 секунд, а не за 11 часов, следующим образом.

1. Используйте функцию Backtracking для поиска пространства F11 ^ 15 или 4 квинтиллиона пространства поиска
2. Функция обратного отслеживания обеспечивает механизм отбрасывания частей пространства поиска, которые не удовлетворяют ограничению (то есть ограничение суммы весов)

Код

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

Тест

# 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')

Выход

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]

Версия генератора

В случае, если мы создадим генератор для весов, который устраняет необходимость сохранения всех весовых векторов 1.9M следующим образом.

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])

Использование

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