1

Нужно получить все комбинации из нескольких (5) неповторяющихся элементов списка lst, удовлетворяющие условию condition. Правильно ли я делаю?

result = []
for i1 in lst[:-4]:
  if condition == False:
    continue
  for i2 in lst[lst.index(i1)+1:-3]:
    if condition == False:
      continue
    for i3 in lst[lst.index(i2)+1:-2]:
      if condition == False:
        continue
      for i4 in lst[lst.index(i3)+1:-1]:
        if condition == False:
          continue
        for i5 in lst[lst.index(i4)+1:]:
          if condition == False:
            continue
          result.append([i1, i2, i3, i4, i5])

UPD:Список вида

players = [
    {'name':'Вася', 'score':1.5, 'price':9.2},
    {'name':'Петя', 'score':1.8, 'price':10.2},
    {'name':'Коля', 'score':2.0, 'price':11.0},
    {'name':'Ира', 'score':1.5, 'price':8.4},
    {'name':'Аня', 'score':2.1, 'price':9.5},
    {'name':'Игнат', 'score':1.4, 'price':7.0},
    {'name':'Полина', 'score':2.0, 'price':14.3},
    {'name':'Юра', 'score':1.6, 'price':8.4},
    ..........................................
]

Список имеет порядка 100 элементов. Нужно получить список комбинаций из 5 неповторяющихся элементов

combs = [{'name':'Вася', 'score':1.5, 'price':9.2},
{'name':'Ира', 'score':1.5, 'price':8.4},
{'name':'Юра', 'score':1.6, 'price':8.4},
{'name':'Игнат', 'score':1.4, 'price':7.0},
{'name':'Аня', 'score':2.1, 'price':9.5}],[...]]

Комбинации должны удовлетворять условию: сумма значений 'price' не должна превышать определенную величину. Список комбинаций необходим для того, чтобы найти комбинацию с максимальной суммой значений 'score'.

2
  • @jfs Отредактировал вопрос
    – Agio
    28 июн 2018 в 14:16
  • на задачу рюкзака отредактированная версия похожа
    – jfs
    28 июн 2018 в 19:21

1 ответ 1

4

Нет, неправильно.

Очевидно, что переменная condition во время перебора нигде не изменяется, соответственно её проверка не имеет никакого смысла.

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

Ну и ещё, обычно такие задачи решаются рекурсивно.

2
  • я имел в виду, что condition это не переменная, а какое-то условие(например, i1 < n, i1 + i2 < n и т.д.) А рекурсивно это как?
    – Agio
    26 июн 2018 в 19:24
  • 1
    @Agio, рекурсивно - это когда функция вызывает саму себя с другими параметрами. Удобно для переменной длины. Соответственно там будет один цикл, а если пора заканчивать, то добавление в результат.
    – Qwertiy
    26 июн 2018 в 19:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.