0

Suppose all the elements of the short list are in the long list, and all elements are unique.
E.g.: 

long = [1,2,3,4,5]  
short = [1,3,5]  
# same_sequence(long, short) = True  
short = [1,4,3]  
# same_sequence(long, short) = False

The one I have in mind is the following, but I'm not sure if it's the best way (corrected thank @abarnert)

def same_sequence(long, short):
    i = -1
    for e in short:
        j = long.index(e, i + 1)
        if j < i:
            return False
        else:
            i = j
    return True
eggplantelf
  • 1,342
  • 2
  • 9
  • 7
  • 3
    What exactly do you mean by "most efficient"? Are you looking for microoptimizatons to an algorithm you already have in mind (if so, which one?), or for an algorithm that's asymptotically optimal in time, or maybe minimal space instead of time, or maybe "short, readable, understandable, maintainable code" rather than space or time, or…? – abarnert Jun 11 '15 at 22:25
  • @vaultah: The accepted answer there is clearly not the most time-efficient or space-efficient, since it copies subarrays and linearly searches them for every step… – abarnert Jun 11 '15 at 22:26
  • @vaultah: Also, at least some of the answers there are looking for an exact subsequence match, not a "sparse" one (in other words, `[2, 3, 4]` would be true, but `[1, 3, 5]` wouldn't). – abarnert Jun 11 '15 at 22:28
  • Another (better): http://stackoverflow.com/questions/23667731/determine-if-all-elements-in-a-list-are-present-and-in-the-same-order-in-another?rq=1 – vaultah Jun 11 '15 at 22:28
  • 1
    Remember a key Python philosophy: write clear code, optimize as necessary. – Alex Huszagh Jun 11 '15 at 22:30
  • 1
    I think [Hetman's solution to vaultah's second possible duplicate](http://stackoverflow.com/a/23668229/908494) is clear, readable, and asymptotically optimal in both time (linear) and space (constant). If you need to micro-optimize the time further, you'll probably need to give us characteristic real-life inputs, and which Python implementation and version you're using (PyPy vs. CPython would definitely make a difference; CPython 3.x vs. 2.x might as well). Anyway, if this is a micro-optimization question, [edit] in more details and it should get re-opened. – abarnert Jun 11 '15 at 22:33
  • thx, by efficient i only mean algorithmic – eggplantelf Jun 11 '15 at 22:36
  • Your code is (a) not correct, and (b) not linear, because it calls `long.index(e)`, which is a linear search _from the start_, for the first instance of `e` in `long`. Also, `index` raises a `ValueError` if it's not found, rather than returning -1. But if you just change it to use `try: i = long.index(e, i+1)` `except ValueError: return False`, I think that solves both problems. – abarnert Jun 11 '15 at 22:41
  • the assumption is that the long list contains all elements in the short list, so there will be no error, but you are right about long.index(e, i+1), thanks – eggplantelf Jun 11 '15 at 22:43
  • @eggplantelf: With that change, you don't need the `j < i` test, because that can never possibly be true. But that also means you can't avoid the `except ValueError:`, because `e` may not be found at all if its last appearance is before `i`, so you might as well write the more robust version. See [my new answer to the linked dup question](http://stackoverflow.com/a/30792705/908494). I think Hetman's answer is still better (it takes a bit more Python knowledge to understand, but it's simpler if you do understand it), but it's probably worth seeing both. – abarnert Jun 11 '15 at 22:49

0 Answers0