0

As part of a dynamical programming assignment, I find myself having to do the following.

I have two sorted lists of length 2 tuples (ordered pairs, representing scores on two criteria). One pair of values can only be considered strictly greater than another if it is greater on one criterion and not lower on the other. So, (1,8) and (2,7) are incomparable, while (1,7) is lower than (2,8).

Each input list contains only values that are incomparable with each other. My method merges the two lists, omitting duplicates as well as any values that are strictly inferior to another value in the new, bigger list. Then it sorts the new list.

For example, the following input produces this result:

combine([(1,8), (2, 6), (3, 4)], [(2, 7), (3, 3)])
[(1, 8), (2, 7), (3, 4)]

Here's the code I have currently produced:

def combine(left, right):
    # start with lists sorted from biggest to smallest
    newlist = left+right
    leftlen = len(left)
    for i in range(leftlen - 1, -1, -1):
        l = newlist[i]  # candidate value to be inserted in
        for j in range(len(newlist) - 1, leftlen - 1, -1):
            r = newlist[j]
            if r[0] >= l[0]:  # cell with >= food encountered without having previously encountered cell with less water
                if r[1] >= l[1]:  # this cell also has more water - del candidate
                    del newlist[i]
                    leftlen -=1
                elif r[0] == l[0]:  # equal food and less water than candidate - candidate wins
                    del newlist[j]
                break  # either way, no need to consider further cells -
                # if this cell doesn't beat candidate, then candidate belongs
            if r[1] <= l[1]:  # cell with less water encountered before cell with more food
                del newlist[j]
                for k in range(j -1, leftlen - 1, -1):  # continue through right list, deleting cells until a value with
                    # higher food is found
                    r = newlist[k]
                    if r[0] > l[0]: break
                    else: del newlist[k]
                break
    newlist.sort(reverse=True)
    return newlist

This code does work, but I am wondering if there is a faster approach to solving this kind of problem? When the lists are long, I end up making a lot of pairwise comparisons.

I've tried to prune out some unnecessary comparisons, relying upon the fact that items in each list are always greater on one criterion and lesser on the other. Thus, the lists are reverse sorted on the first value in the tuple, and therefore also sorted on the second value!

One idea I had was to try and use a different ADT - some type of tree perhaps, but I'm not sure if this is going to help or not.

Any suggestions? This is for an assignment, so I'm looking for ideas rather than for somebody to rewrite the whole thing for me :) Cheers!

BlatantMacaroon
  • 1
  • 3
  • 1
    @Prune the mentioned question asks a question related to graph but this question seems different. Can you educate me how this problem transforms to a graph problem? – Zabir Al Nazi May 15 '20 at 04:51
  • 1
    Hmm, yeah, I'm not 100% sure that's the same question. If it is, it's not obvious why to me. – BlatantMacaroon May 15 '20 at 05:17
  • Anyway, I think I've answered it for myself. This accomplishes the same thing with only the complexity of a sort: def combine(left, right): newlist = left+right newlist.sort() for i in range(len(newlist) -2, -1, -1): if newlist[i][0] == newlist[i+1][0] or newlist[i][1] <= newlist[i+1][1]: del newlist[i] return newlist – BlatantMacaroon May 15 '20 at 05:18
  • Are you sure this works for all cases? I also came up with a greedy solution and wanted to answer but then it got closed. – Zabir Al Nazi May 15 '20 at 05:23
  • Not absolutely sure! It seems to work with the inputs I've tried so far... – BlatantMacaroon May 15 '20 at 05:35
  • It works (if it does!) on the fact that when sorted, a compliant list will have value[0] in strictly ascending order and value[1] in strictly descending order. If you run backwards through the list, then there are two ways this might be violated. Either list[i][0] is equal rather than less than list[i+1][0] (because the list is sorted, it cannot be more) then remove list[i] (if equal on value[0], they will be sorted by value[1] because of the way python sorts tuples - therefore list[i] should be removed, rather than list[i+1] – BlatantMacaroon May 15 '20 at 05:40
  • The other possible violation is that list[i][1] is <= list[i+1][1] - in which case list[i] is strictly less than list[i+1] and can be safely removed. – BlatantMacaroon May 15 '20 at 05:42

0 Answers0