Предположим, у меня есть следующее: arr = [0, 0, 0], [20, 20, 90], [30, 30, 50], [40, 40, 80], [10, 75, 10], [100, 100, 0]
Я строю из него комбинацию print(list(itertools.combinations(arr, 2)))
Таким образом, я получаю хорошие все комбинации - только движение "вперед", что здорово:
[([0, 0, 0], [20, 20, 90]), ([0, 0, 0], [30, 30, 50]), ([0, 0, 0], [40, 40, 80]), ([0, 0, 0], [10, 75, 10]), ([0, 0, 0], [100, 100, 0]), ([20, 20, 90], [30, 30, 50]), ([20, 20, 90], [40, 40, 80]), ([20, 20, 90], [10, 75, 10]), ([20, 20, 90], [100, 100, 0]), ([30, 30, 50], [40, 40, 80]), ([30, 30, 50], [10, 75, 10]), ([30, 30, 50], [100, 100, 0]), ([40, 40, 80], [10, 75, 10]), ([40, 40, 80], [100, 100, 0]), ([10, 75, 10], [100, 100, 0])]
НО есть хитрость - я должен добавить все дополнительные расходы за пропущенные очки.
Скажите, в случае ([0, 0, 0], [40, 40, 80])
Я пропустил эти [20, 20, 90], [30, 30, 50]
Для которых есть дополнительная накопленная стоимость расстояния от 0,0,0 до тока, равного 140, что добавляет третье пропущенное значение, равное (50+90) , Эти расстояния индивидуально я хотел бы внести в список кортежей. Доступ к предыдущим пунктам в списке, который я сделал ниже, но накопление для каждой комбинации дало мне головную боль.
Какая структура данных или evtl. алгоритм угнанной комбинации будет поддерживать пропущенные предыдущие дополнительные расходы, все еще создавая комбинацию для списка n?
Так что я подумал и о более ручном подходе:
`def combination(given_list, possibilities):
penalty = 0
final_list = []
if possibilities == 0: return [[]]
for item in range(0, len(given_list)):
current_item = given_list[item]
remaining_from_given_list = given_list[item + 1:]
for prev in combination(remaining_from_given_list, possibilities -1):
penalty += previous_item[2]
final_list.append([current_item] + prev)
penalty = 0
return final_list
`
Но это только дало мне предыдущие штрафы, что тогда не справедливо для всех случаев (0, если я не пропустил предыдущий, все предыдущие дополнительные расходы, которые я пропустил)
Но не уверен, как угнать вышеупомянутое, чтобы измерить расстояние и получить накопление для всех предыдущих значений.
Конечный результат будет выглядеть следующим образом:
ways = [("0", "1", 0), ("0", "2", 90), ("0", "3", 140), ("0", "4", 220), ("0", "5", 230), ("1", "2", 0), ("1", "3", 50), ("1", "4", 130), ("1", "5", 140), ("2", "3", 0), ("2", "4", 80), ("2", "5", 900), ("3", "4", 0), ("3", "5", 10), ("4", "5", 0)]
Оптимальный путь, который я использую для вычисления dijkstra, у меня уже есть эта часть, и если я создаю список Кортежи вручную, как это, это работает, как ожидалось.
Я чувствую, что упускаю что-то очевидное - может быть, я должен использовать словарь, чтобы достичь этого? Я также подумал о двойном связанном списке, но это, вероятно, тоже не лучший подход.