CODEWITHSUNDEEP
python
roushrsh
roushrsh

Reputation: 91

Writing function to find longest path through list (recursion maybe?)

I have a sorted list of up to 50 items as so: [50,120,160,180,190,250,260,280,300,400,410,475]

and I have legal possible 'spaces' in another list (about 20): [30, 60, 70]

basically I'm trying to figure out the longest line possible using those spaces as the allowed amount between each value

That is in this case, we'd have 50,120,180,250,280 as our longest line (5 items).

Upvotes: 2

Views: 114

Answers (3)

jirassimok
jirassimok

Reputation: 4293

One possible naive solution would be to iterate over the list, keeping a list of every possible subsequence that fits the requirement.

def longest_spaced_subsequence(values, spaces):
    candidates = []
    for element in values:
        # look at each of the subsequences
        for i in range(len(candidates)):
            candidate = candidates[i]

            # if the new element has good spacing from
            # the highest in the candidate, add it.
            if element - candidate[-1] in spaces:
                # make a copy and and add the element to it
                new = list(candidate)
                new.append(element)
                candidates.append(new)

        # maybe this element is the start of the longest sequence
        candidates.append([element])

    return max(candidates, key=len)

This is far from the most efficient algorithm, but it works.

There is one area where this naive algorithm really needs improvement: it keeps all of the candidate lists forever, so it takes up far more memory than it needs to. To save memory, you just need to remove short candidates that can't be extended any more, which is only a little trickier than it sounds.

As you guessed in the question title, recursion could help with this problem as well. You could take a greedy approach a bit more like Samuel Elh's answer, but instead of just returning the result, you have to keep going and make sure that it's really the longest.

Upvotes: 1

Kelly Bundy
Kelly Bundy

Reputation: 27660

Remembering for each item a longest path ending with that item:

>>> p = {}
>>> for i in items:
        p[i] = max((p.get(i - s, []) for s in spaces), key=len) + [i]

>>> max(p.values(), key=len)
[50, 120, 190, 250, 280]

Upvotes: 4

Ismail
Ismail

Reputation: 743

Hopefully I understood from your example:

base_list = [50,120,160,180,190,250,260,280,300,400,410,475]
spaces = [30, 60, 70]

def calculate(base):
    for i,x in enumerate(base):
        if 0 == i or (base[i] - base[i-1]) in spaces:
            continue
        else:
            del base[i]
            return calculate(base)

    return base

print( calculate(base_list[:]) )

Upvotes: 1

Related Questions