Geek asks and answers

Search for an algorithm for combining tuples containing repeating fields in a list of tuples

I am trying to find a better way to handle what surface turned out to be a simple task in python 2.7.

I have a list containing tuples.
Each tuple contains 2 dictionaries, each of which has 2 fields: 'alt' and 'id'. The 'id' is always the same for every item in the list and is mostly ignored for this question.

It looks something like this:

[
  ({id:1, alt: 10},{id:1, alt: 12}),
  ({id:1, alt: 8},{id:1, alt: 9}),
  ({id:1, alt: 9},{id:1, alt: 10})
]

Sometimes the value of the "alt" field of the dictionary with 1 index will be the same as the "alt" value of the field of the 0-index dictionary of the next element in the list. In the above example, you can see that when alt = 9 in the second and third elements of the list.

When this happens, I want to combine these 2 tuples into one tuple, where the alt value of the 1-index dictionary of the first tuple will be equal to the alt value of the 1-index dictionary of the second tuple, overriding the "duplicate alt values:

From this:

[
  ({id:1, alt: 8},{id:1, alt: 9}),
  ({id:1, alt: 9},{id:1, alt: 10})
]

:

[
  ({id:1, alt: 8},{id:1, alt: 10})
]

However, there are times when this pattern occurs for several tuples in the list, and therefore merging should occur through several tuples:

From this:

[
  ({id:1, alt: 8},{id:1, alt: 9}),
  ({id:1, alt: 9},{id:1, alt: 9}),
  ({id:1, alt: 9},{id:1, alt: 10}),
  ({id:1, alt: 10},{id:1, alt: 7}),
  ({id:1, alt: 8},{id:1, alt: 9}),
  ({id:1, alt: 9},{id: 1, alt: 10})
]

:

[
  ({id:1, alt: 8},{id:1, alt: 7}),
  ({id:1, alt: 8},{id:1, alt: 10})
]

I tried several approaches and I think that some kind of recursion is needed here, but processing the last case, when I need to check sequential tuples and merging between them, causes me to hit the wall. Any suggestions would be highly appreciated.

+3
source share
1 answer
def merge(xs):
    it = iter(xs)
    ret = next(it, (None, None))
    for x in it:
        if ret[1] is None or x[0]['alt'] != ret[1]['alt']:
            yield ret
            ret = x
        else:
            ret = ret[0], x[1]
    if ret[0] is not None:
        yield ret

Example:

>>> data = [
...     ({'id':1, 'alt': 8}, {'id':1, 'alt': 9}),
...     ({'id':1, 'alt': 9}, {'id':1, 'alt': 9}),
...     ({'id':1, 'alt': 9}, {'id':1, 'alt': 10}),
...     ({'id':1, 'alt': 10}, {'id':1, 'alt': 7}),
...     ({'id':1, 'alt': 8}, {'id':1, 'alt': 9}),
...     ({'id':1, 'alt': 9}, {'id': 1, 'alt': 10})
... ]
>>> list(merge(data))
[({'alt': 8, 'id': 1}, {'alt': 7, 'id': 1}),
 ({'alt': 8, 'id': 1}, {'alt': 10, 'id': 1})]

>>> data = [
...   ({'id':1, 'alt': 10}, {'id':1, 'alt': 12}),
...   ({'id':1, 'alt': 8}, {'id':1, 'alt': 9}),
...   ({'id':1, 'alt': 9}, {'id':1, 'alt': 10})
... ]
>>> list(merge(data))
[({'alt': 10, 'id': 1}, {'alt': 12, 'id': 1}),
 ({'alt': 8, 'id': 1}, {'alt': 10, 'id': 1})]

>>> list(merge([]))
[]
+2
source

More articles:


All Articles