Iterate on two lists and sync them

Question

I need to iterate on two lists in the following way:

Pseudo code:

j=1
for i=1 to n:
   print a[i], b[j]
   while b[j+1] <= a[i]:
      j++
      print a[i], b[j]

For example:

a = [1 3 5 7]
b = [2 4 9]

Desired output:

How do you do it cleanly in python?

The question seems incomplete to me, can you explain your output based on the two input lists? What happened to the `9`? — Levon, Aug 06 '12 at 17:13
@Levon the `9` doesn't show up in the output of the pseudocode, as my translated Python shows. — murgatroid99, Aug 06 '12 at 17:25

score 7 · Accepted Answer · edited May 23 '17 at 11:45

Your pseudo code will almost work in Python. Some working code that does what you want is:

a = [1, 3, 5, 7]
b = [2, 4, 9] 
j = 0
for i in range(len(a)):
    print a[i], b[j]
    while j<len(b)-1 and b[j+1] <= a[i]:
        j += 1
        print a[i], b[j]

Note the few changes to make it work in Python:

When declaring the list, commas are required between items.
List indices start at 0, so both i and j should start there.
len(a) returns the length of a (4 in this case), and iterating i through range(len(a)) executes the loop for each integer from 0 to len(a)-1, which is all of the indices in a.
The ++ operation is not supported in Python, so we use j +=1 instead.
We have to avoid using out of bounds indices of b, so we test to make sure j will be in bounds before incrementing it.

This code can be made more pythonic by iterating through the list as follows:

a = [1, 3, 5, 7]
b = [2, 4, 9] 
j = 0
for element in a:
   print element, b[j]
   while j<len(b)-1 and b[j+1] <= element:
      j += 1
      print element, b[j]

In general, you probably don't want to just print list elements, so for a more general use case you can create a generator, like:

def sync_lists(a, b)
    if b:
        j = 0
        for element in a:
            yield (element, b[j])
            while j<len(b)-1 and b[j+1] <= element:
                j += 1
                yield (element, b[j])

And then you can print them as before with

a = [1, 3, 5, 7]
b = [2, 4, 9]
for (e1, e2) in sync_lists(a, b):
    print e1, e2

Yeah, this seems just unusual enough that a direct translation of the pseudocode is probably simpler than some games with `next` and `itertools`. I might wrap up this iteration logic in a generator, though, which seems to me the most Pythonic "home" for quirky iteration logics. — DSM, Aug 06 '12 at 17:25
I'm curious -- you recommend using `enumerate`, but it doesn't look like you're using `i`. Wouldn't it be easier just to iterate over the list? — Sam Mussmann, Aug 06 '12 at 17:35
@SamMussmann you're right, I missed that. For some reason I thought I still needed the index into `a`. — murgatroid99, Aug 06 '12 at 17:36

score 2 · Answer 2 · edited May 23 '17 at 12:15

2

The generator code in murgatroid99's answer can be generalised to any iterables (as opposed to sequences only) by using next() instead of index arithmetic:

def sync_list(a, b):
    b = iter(b)
    y, next_y = next(b), next(b)
    for x in a:
       yield x, y
       while next_y <= x:
          y, next_y = next_y, next(b)
          yield x, y

edited May 23 '17 at 12:15

Community

1
1

answered Aug 06 '12 at 18:45

Sven Marnach

574,206
118
941
841

Note that with the wrong arrays, you might start getting `StopIteration` exceptions. I modified my code to avoid the corresponding `IndexError`s. – murgatroid99 Aug 07 '12 at 13:09
1

@murgatroid99: `StopIteration` is handled by a caller e.g., a for-loop. No special handling is required in the generator for "wrong" arrays. – jfs Aug 07 '12 at 13:24
@J.F.Sebastian but `b` is not being iterated through in a for-loop, so the caller *is* `sync_list`. Calling [`next`](http://docs.python.org/library/functions.html#next) can raise that exception, and using it in a loop doesn't magically handle it. – murgatroid99 Aug 07 '12 at 13:26
@murgatroid99: If `StopIteration` is raised inside a generator, this terminates the generator. I think this is the more reasonable behaviour than breaking the invariants (which is what your new code does in case `b` is too short). – Sven Marnach Aug 07 '12 at 13:28
@murgatroid99: The example caller is `for e1, e2 in sync_lists(a, b):`. It handles `StopIteration` transparently – jfs Aug 07 '12 at 13:29
@SvenMarnach since no invariants were given, I can't comment on whether my code breaks them, but I see you are right about the exception. – murgatroid99 Aug 07 '12 at 13:33
@murgatroid99: I interpreted `y <= x` for all yielded pairs as the desired invariant, but you are right that this hasn't been clearly specified (and none of the suggested code snippets checks this for the first pair). – Sven Marnach Aug 08 '12 at 17:55

Iterate on two lists and sync them

2 Answers2