python - comparing order of list without sorting existing data

Question

I am sorry if the title is little confusing but its not really that complicated either. I am trying to implement a logic where I will be just printing out list items which have correct order as per another list. For example let's say I have following lists:

a = [(299,70), (323,70), (448,70), (548,70), (613,70), (745,70)]
b = [(613,70), (448,70), (548,70), (323,70), (299,70)]

What I want

I want to print output of such elements in list b which are in same order as in list a. In above case it can be seen that only two elements are following the order in b and they are:

c= [(448,70), (548,70)]

P.S. I am comparing b with a and intending to keep the order of b same as it was generated in my program. I DON'T want to use any sorting method that can alter the order of existing b list.

The reason for not using sorting is the task I am working on has a list as a reference and b list is my implementation. so after b is generated I simply want to print such elements which have matching order without altering(changing order) any element during comparison.

What I tried

I tried comparing indexes of numbers inside the list instead of values, but it yields no satisfactory results. Additionally this method fails terribly when two lists are of different size as in above case.

EDIT:

Sorry for all the confusions. As asked here is one more example of same kind and more clear description of what I want.

I have two lists of tuples as given below:

list1 = [(1,2),(3,4),(5,6),(7,8),(9,10)]
list2 = [(1,2),(5,6),(3,4),(7,8),(9,10)]

I want to print out consecutive pairs of tuples in list2 which are in same order as given in list1. So in this example the output should be

list3 = [(7,8),(9,10)]

No matter what is the size of both the lists, what I want is only the common consecutive tuples to be printed which are present in both.

It's not very clear (to me) what you mean by "following the same order". Do you mean the order of elements in the tuples or in the list? Can you give an example where you don't use tuples? — loopbackbee
– loopbackbee, Commented Jul 20, 2015 at 13:15
What do you mean by "elements in list b which are in same order as in list a"? Can you define your criterion more precisely? — adrianus
– adrianus, Commented Jul 20, 2015 at 13:15
Are you looking for: the longest string of elements from b which follow the order from a? the longest string of consecutive elements from b which follow the order from a? the longest string of consecutive elements from b which appear consecutively and in the same order in a? to take the first element from b which appears in a, then the next element from b which appears later in a, and so on? all pairs of elements from b which appear in the same order in a? things which appear in the same position in b, after some reordering, as they do in a? More examples would help — jwg
– jwg, Commented Jul 20, 2015 at 13:16
c = [t1 for t1, t2 in itertools.product(a, b) if t1 == t2]? Or do you mean something more complicated? Your example is not terribly enlightening. — jonrsharpe
– jonrsharpe, Commented Jul 20, 2015 at 13:18

jonrsharpe · Accepted Answer · 2015-07-20 13:40:18Z

4

If I've correctly understood, what you're trying to do, you could use a difflib.SequenceMatcher, whose get_matching_blocks method will, per the documentation:

Return list of triples describing matching subsequences

to implement it:

from difflib import SequenceMatcher

def find_subseq(seq1, seq2):
    """Find matching subsequences of the two argument sequences."""
    matcher = SequenceMatcher(None, seq1, seq2, False)
    out = []
    for start, _, size in matcher.get_matching_blocks():
        if size > 1:
            out.extend(seq1[start:start+size])
    return out

In use:

>>> a = [(299, 70), (323, 70), (448, 70), (548, 70), (613, 70), (745, 70)]
>>> b = [(613, 70), (448, 70), (548, 70), (323, 70), (299, 70)]
>>> find_subseq(a, b)
[(448, 70), (548, 70)]

edited Jul 20, 2015 at 13:40

answered Jul 20, 2015 at 13:32

jonrsharpe

123k31 gold badges277 silver badges488 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Radheya Over a year ago

Wow thank you very much man! Sorry for all the hassle. This is perfect. I was just looking to more solutions and trying to re-edit my question.

jonrsharpe Over a year ago

@DhruvJ don't stop editing the question; you may yet get better answers if you can provide a clear description of what you're trying to do

Radheya Over a year ago

Yea sure. I will add some more examples and description. I am also going through documentation of SequenceMatcher

adrianus · Accepted Answer · 2015-07-20 13:38:30Z

2

Since you were talking in the comments about consecutive matching elements, you can check for those as follows:

a = [(299,70), (323,70), (448,70), (548,70), (613,70), (745,70)]
b = [(613,70), (448,70), (548,70), (323,70), (299,70)]

for i in range(len(a)-1):
    if a[i] in b and b.index(a[i]) < len(b) - 1 and b[b.index(a[i])+1] == a[i+1]:
        print a[i], a[i+1]

Result:

>>> 
(448, 70) (548, 70)

answered Jul 20, 2015 at 13:38

adrianus

3,2411 gold badge25 silver badges42 bronze badges

1 Comment

Radheya Over a year ago

This is very useful as i don't even need to import any libraries. Super.

Collectives™ on Stack Overflow

python - comparing order of list without sorting existing data

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related