Q:

Python combination with a twist

Assume I have following:
arr = [0, 0, 0], [20, 20, 90], [30, 30, 50], [40, 40, 80], [10, 75, 10], [100, 100, 0]
I build a combination from it
print(list(itertools.combinations(arr, 2)))
So I get a nice all combinations - only moving "forward" which is great:
[([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])]
BUT there is a trick - I have to add all additional costs for the points I've skipped. 
Say in the case of ([0, 0, 0], [40, 40, 80])
I have skipped these ones [20, 20, 90], [30, 30, 50]
For which have the additional accumulated cost of distance from 0,0,0 until current which is 140, which is adding the skipped's third values which is (50+90).  These distances individually I would like to put into a list of tuples.  Accessing the previous items in the list I've done below, but accumulating for each combination gave me the headache. 
What data structure or evtl.  hijacked combination algorithm would maintain the skipped previous additional costs still creating the combination for an n list? 
So I thought about a more manual approach as well:
`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
`

But this only gave me the previous penalties which then is not true for all cases (0 if I don't miss the previous, all the previous additional cost(s) which I have missed)
But not sure how to hijack the above to measure distance and get the accumulation for all previous values. 
The final result would look like:

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

The optimal path I am using a dijkstra to calculate, I have that part already and if I create the list of tuples manually like this, it works as expected. 
I feel like I am missing something obvious - maybe I should use a dictionary to achieve this?  I thought about a double linked list as well but that's likely not the best approach either. 

A:

Try an iterative approach:
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)]

