Python 组合与扭曲

Question

假设我有以下内容： 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)))

所以我得到了一个很好的所有组合 - 只移动 "forward" 这很棒：

[([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 计算的最佳路径，我已经有了那部分，如果我像这样手动创建元组列表，它会按预期工作。

我觉得我遗漏了一些明显的东西 - 也许我应该使用字典来实现这一点？我也考虑过双链表，但这也可能不是最好的方法。

Answer 1

尝试迭代方法：

arr = [[0, 0, 0], [20, 20, 90], [30, 30, 50], [40, 40, 80], [10, 75, 10], [100, 100, 0]]

ways = []

total = len(arr)
for i in range(total):
    for j in range(i + 1, total):
        ways.append((i, j, sum(i[-1] for i in arr[i+1:j])))

print(ways)

Returns:

[(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, 90), 
 (3, 4, 0), (3, 5, 10), (4, 5, 0)]

Python 组合与扭曲

Python combination with a twist

python

graph

linear-algebra