15

I want to merge two lists in Python, with the lists being of different lengths, so that the elements of the shorter list are as equally spaced within the final list as possible.

i.e. I want:

l1 = [1, 2, 3, 4]
l2 = ['a', 'b']

output = [1, 'a', 2, 3, 'b', 4]

It needs to be able to function with lists that aren't exact multiples too, so it could take:

l1 = [1, 2, 3, 4, 5]
l2 = ['a', 'b', 'c']

and produce [1, 'a', 2, 'b', 3, 'c', 4, 5] or similar.

It needs to preserve the ordering of both lists.

I can see how to do this by a long-winded brute force method but since Python seems to have a vast array of excellent tools to do all sorts of clever things which I don't know about (yet), I wondered whether there's anything more elegant I can use?

If you want regular interleaving (equal-spaced), see How to interleave two lists of different length?.

3
  • Why the 'b' comes between 3 and 4?
    – kennytm
    Commented Oct 10, 2013 at 10:43
  • Because it spaces them evenly within the list. I'd take ['a, 1, 2, 'b', 3, 4] as well but the rotation looks nicer to my eye.
    – Jack Aidley
    Commented Oct 10, 2013 at 10:45
  • docs.python.org/2/library/functions.html#slice might help. See also the itertools module. Now the important part here is the algorithm, not the tools themselves.
    – bruno desthuilliers
    Commented Oct 10, 2013 at 10:46

10 Answers 10

Reset to default
12

Borrowing heavily from Jon Clements' solution, you could write a function that takes an arbitrary number of sequences and returns merged sequence of evenly-spaced items:

import itertools as IT

def evenly_spaced(*iterables):
    """
    >>> evenly_spaced(range(10), list('abc'))
    [0, 1, 'a', 2, 3, 4, 'b', 5, 6, 7, 'c', 8, 9]
    """
    return [item[1] for item in
            sorted(IT.chain.from_iterable(
            zip(IT.count(start=1.0 / (len(seq) + 1), 
                         step=1.0 / (len(seq) + 1)), seq)
            for seq in iterables))]

iterables = [
    ['X']*2,
    range(1, 11),
    ['a']*3
    ]

print(evenly_spaced(*iterables))

yields

[1, 2, 'a', 3, 'X', 4, 5, 'a', 6, 7, 'X', 8, 'a', 9, 10]
1
  • Sorting isn't stable. You can fix it by putting operator.itemgetter(0) as the sort key. BTW I posted my own answer that includes the fix.
    – wjandrea
    Commented Jan 4, 2020 at 20:26
11

This is basically the same as Bresenham's line algorithm. You can calculate "pixel" positions and use them as the indices into the lists.

Where your task differs is that you only want each element to show up once. You'd need to either modify the algorithm or post-process the indices, appending the elements from the lists only the first time they appear. There is a slight ambiguity, though: when both pixel/list indices change at the same time, you'll need to pick which one to include first. This corresponds to the two different options for interleaving the lists that are mentioned in the question and a comment.

2
7

With the assumption that a is the sequence to be inserted into:

from itertools import izip, count
from operator import itemgetter
import heapq

a = [1, 2, 3, 4]
b = ['a', 'b']

fst = enumerate(a)
snd = izip(count(0, len(a) // len(b)), b)
print(map(itemgetter(1), heapq.merge(fst, snd)))
# [1, 'a', 2, 3, 'b', 4]
4
  • @JackAidley ugh - of course in Python 3.x you will - one sec ;)
    – Jon Clements
    Commented Oct 10, 2013 at 12:13
  • clever. For python3 it's probably neater to use a list comprehension than list(map(...))
    – John La Rooy
    Commented Oct 10, 2013 at 12:49
  • 1
    Update Python 3.5+, the latter will not work. heapq.merge() accepts a key function, e.g. [x for i, x in heapq.merge(fst, snd, key=lambda x: x[0])]
    – pylang
    Commented Oct 11, 2018 at 2:10
  • While the logic seems quite neat, the result is lop-sided: "AAAAAAAAAAA" & "BBB" -> ABAAABAAABAAAA. (one A at the start, 4 at the end).
    – ideasman42
    Commented May 23 at 0:25
5

if a is the longer list and b is the shorter

from itertools import groupby

len_ab = len(a) + len(b)
groups = groupby(((a[len(a)*i//len_ab], b[len(b)*i//len_ab]) for i in range(len_ab)),
                 key=lambda x:x[0])
[j[i] for k,g in groups for i,j in enumerate(g)]

eg

>>> a = list(range(8))
>>> b = list("abc")
>>> len_ab = len(a) + len(b)
>>> groups = groupby(((a[len(a)*i//len_ab], b[len(b)*i//len_ab]) for i in range(len_ab)), key=lambda x:x[0])
>>> [j[i] for k,g in groups for i,j in enumerate(g)]
[0, 'a', 1, 2, 'b', 3, 4, 5, 'c', 6, 7]

You can use this trick to make sure a is longer than b

b, a = sorted((a, b), key=len)
5
  • This was the solution I went with in the end although I amended the final line to [j[i] for _,g in groups for i,j in enumerate(g)] so as to suppress a warning about an unused variable.
    – Jack Aidley
    Commented Oct 14, 2013 at 9:50
  • @ideasman42, I tested it works in 3.11 [j[i].. is not the same as j[1][i] did you possibly copy it incorrectly.
    – John La Rooy
    Commented May 24 at 2:31
  • @ideasman42, At the very top it says a is longer than b. Can you try swapping them?
    – John La Rooy
    Commented May 24 at 4:54
  • @ideasman42, I think maybe this answer doesn't work properly though. Good on you for finding out after all this time.
    – John La Rooy
    Commented May 24 at 5:53
  • Removed own noisy comments and fixed the answer for Python3 range(..) -> list(range(..)) was the issue.
    – ideasman42
    Commented May 26 at 4:30
4

If we modify @Jon's answer like this

from itertools import count
import heapq

[x[1] for x in heapq.merge(izip(count(0, len(b)), a), izip(count(0, len(a)), b))]

It doesn't matter which of a/b is longest

3

I like unutbu's answer but not the nested style, so I rewrote it. While I was there I noticed the sorting wasn't stable, so I fixed it using operator.itemgetter.

I also replaced itertools.count with enumerate because it's more intuitive. As a bonus it should also be more accurate for large inputs, though I haven't tested it.

import itertools
import operator

def distribute(sequence):
    """
    Enumerate the sequence evenly over the interval (0, 1).

    >>> list(distribute('abc'))
    [(0.25, 'a'), (0.5, 'b'), (0.75, 'c')]
    """
    m = len(sequence) + 1
    for i, x in enumerate(sequence, 1):
        yield i/m, x

def intersperse(*sequences):
    """
    Evenly intersperse the sequences.

    Based on https://stackoverflow.com/a/19293603/4518341

    >>> list(intersperse(range(10), 'abc'))
    [0, 1, 'a', 2, 3, 4, 'b', 5, 6, 7, 'c', 8, 9]
    >>> list(intersperse('XY', range(10), 'abc'))
    [0, 1, 'a', 2, 'X', 3, 4, 'b', 5, 6, 'Y', 7, 'c', 8, 9]
    >>> ''.join(intersperse('hlwl', 'eood', 'l r!'))
    'hello world!'
    """
    distributions = map(distribute, sequences)
    get0 = operator.itemgetter(0)
    for _, x in sorted(itertools.chain(*distributions), key=get0):
        yield x

Note that there's one difference from your second example, where 'b' and 'c' get moved down:

>>> list(intersperse(range(1, 6), 'abc'))
[1, 'a', 2, 3, 'b', 4, 'c', 5]
1

A variant of @Jon Clements answer using more_itertools.collate with explanation.

Given

import itertools as it

import more_itertools as mit


a, b = range(1, 5), ["a", "b"]

Code

first = enumerate(a)
second = zip(it.count(0, len(a) // len(b)), b)
[x for i, x in mit.collate(first, second, key=lambda x: x[0])]
# [1, 'a', 2, 3, 'b', 4]

Details

This answer is updated to use with Python 3.

first and second are iterables of tuples, each tuple comprising a position-element pair.

list(first)
# [(0, 1), (1, 2), (2, 3), (3, 4)]

list(second)
# [(0, 'a'), (2, 'b')]

more_itertools.collate() wraps heapq.merge(), which merges the pre-sorted first and second iterables in order. In the final list comprehension, the key is the sorting function while the last element in each tuple in returned.

See Also

Install this third-party package via > pip install more_itertools

0

If we want to do this without itertools:

def interleave(l1, l2, default=None):  
    max_l = max(len(l1), len(l2))
    data  = map(lambda x: x + [default] * (max_l - len(x)), [l1,l2])
    return [data[i%2][i/2] for i in xrange(2*max_l)]

Ahh, missed the equally spaced part. This was for some reason marked as duplicate with a question that didn't require equally spaced in the presence of differing list lengths.

1
  • Thanks for answering a question and welcome to SO. For your future reference, your edited comment probably isn't necessary (you could have posted it when you made your edit there) or you could indicated that you edited post, e.g., "Edit I missed ..."
    – Richard Erickson
    Commented Jun 17, 2015 at 23:47
0

This is a solution distributes evenly, assuming start/end values may wrap: e.g.
("-------", "**") --> "--*---*--".

A simplified version of Bresenham's line algorithm is used to ensure even distribution.

The implementation here also gives a symmetrical distribution.

from typing import (
    Any,
    Generator,
    List,
)


def plot_line_v2(delta_x: int, delta_y: int) -> Generator[bool, None, None]:
    # Perform Bresenham's calculation for 2D line drawing,
    # simplified to yield booleans that selects between sequences.
    assert delta_x >= delta_y
    delta_x_step = 2 * delta_x
    delta_y_step = 2 * delta_y
    error = delta_y_step - delta_x
    delta_x_step -= delta_y_step
    for _ in range(delta_x):
        if error >= 0:
            error -= delta_x_step
            yield True
        else:
            error += delta_y_step
            yield False


def interleave_lists_apply(a: List[Any], b: List[Any]) -> Generator[Any, None, None]:
    if len(a) == 0:
        yield from b
        return
    if len(b) == 0:
        yield from a
        return
    if len(a) == len(b):
        for i in range(len(a)):
            yield a[i]
            yield b[i]
        return

    # Simplifies distribution when size is always ordered.
    if len(a) < len(b):
        a, b = b, a

    a_index = 0
    b_index = 0

    # Swap the bias after `a_len_half` for a "symmetrical" result.
    a_len_half = len(a) // 2
    for test in plot_line_v2(len(a), len(b)):
        if a_index <= a_len_half:
            yield a[a_index]
            a_index += 1
            if test:
                yield b[b_index]
                b_index += 1
        else:
            if test:
                yield b[b_index]
                b_index += 1
            yield a[a_index]
            a_index += 1

    assert a_index == len(a)
    assert b_index == len(b)

This is the result of interleaving multiple stings:

width = 80
for x in range(width):
    n_full = x + 1
    n_empty = width - n_full
    a = '*' * n_full
    b = '-' * n_empty
    print("".join(interleave_lists_apply(list(a), list(b))))

The resulting output.

----------------------------------------*---------------------------------------
--------------------*--------------------------------------*--------------------
-------------*--------------------------*-------------------------*-------------
----------*-------------------*------------------*-------------------*----------
--------*---------------*---------------*--------------*---------------*--------
-------*------------*------------*------------*------------*------------*-------
------*----------*-----------*----------*---------*-----------*----------*------
-----*---------*---------*---------*--------*---------*---------*---------*-----
----*--------*--------*--------*--------*-------*--------*--------*--------*----
----*-------*-------*-------*-------*------*-------*-------*-------*-------*----
----*------*------*------*-------*------*-----*-------*------*------*------*----
---*------*------*-----*------*------*----*------*------*-----*------*------*---
---*-----*-----*------*-----*-----*-----*----*-----*-----*------*-----*-----*---
---*-----*----*-----*-----*----*-----*----*-----*----*-----*-----*----*-----*---
---*----*----*-----*----*----*-----*----*---*-----*----*----*-----*----*----*---
--*----*----*----*----*----*----*----*---*----*----*----*----*----*----*----*---
--*----*----*---*----*----*----*---*----*---*---*----*----*----*---*----*----*--
--*----*---*----*---*---*----*---*----*--*----*---*----*---*---*----*---*----*--
--*---*----*---*---*---*---*----*---*---*--*---*----*---*---*---*---*----*---*--
--*---*---*---*---*---*---*---*---*---*--*---*---*---*---*---*---*---*---*---*--
--*---*---*--*---*---*---*---*--*---*---*--*---*--*---*---*---*---*--*---*---*--
--*--*---*---*--*---*---*--*---*---*--*--*--*---*---*--*---*---*--*---*---*--*--
--*--*---*--*---*--*---*--*---*--*---*--*-*---*--*---*--*---*--*---*--*---*--*--
--*--*--*---*--*--*---*--*--*---*--*--*--*--*--*---*--*--*---*--*--*---*--*--*--
--*--*--*--*--*---*--*--*--*--*---*--*--*-*--*---*--*--*--*--*---*--*--*--*--*--
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
-*--*--*--*--*--*--*--*--*--*--*--*--*--*-*--*--*--*--*--*--*--*--*--*--*--*--*-
-*--*--*--*--*--*--*-*--*--*--*--*--*--*-*-*--*--*--*--*--*-*--*--*--*--*--*--*-
-*--*--*--*-*--*--*--*-*--*--*--*-*--*--*-*--*-*--*--*--*-*--*--*--*-*--*--*--*-
-*--*--*-*--*--*-*--*--*-*--*--*-*--*--*-*-*--*-*--*--*-*--*--*-*--*--*-*--*--*-
-*--*-*--*--*-*--*-*--*--*-*--*-*--*-*--*-*-*--*-*--*-*--*--*-*--*-*--*--*-*--*-
-*--*-*--*-*--*-*--*-*--*-*--*-*--*-*--*-*-*-*--*-*--*-*--*-*--*-*--*-*--*-*--*-
-*--*-*-*--*-*--*-*--*-*-*--*-*--*-*--*-**--*-*--*-*--*-*-*--*-*--*-*--*-*-*--*-
-*--*-*-*--*-*-*--*-*-*--*-*-*--*-*-*--*-*-*-*-*--*-*-*--*-*-*--*-*-*--*-*-*--*-
-*-*--*-*-*--*-*-*-*--*-*-*--*-*-*-*--*-**--*-*-*-*--*-*-*--*-*-*-*--*-*-*--*-*-
-*-*--*-*-*-*-*--*-*-*-*--*-*-*-*-*--*-*-**--*-*-*-*-*--*-*-*-*--*-*-*-*-*--*-*-
-*-*-*--*-*-*-*-*-*--*-*-*-*-*-*--*-*-*-**-*-*--*-*-*-*-*-*--*-*-*-*-*-*--*-*-*-
-*-*-*-*-*--*-*-*-*-*-*-*-*-*--*-*-*-*-*-**-*-*-*--*-*-*-*-*-*-*-*-*--*-*-*-*-*-
-*-*-*-*-*-*-*-*-*-*--*-*-*-*-*-*-*-*-*-**-*-*-*-*-*-*-*-*--*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-**-*-*-*-*-*-*-*-*-*--*-*-*-*-*-*-*-*-**-*-*-*-*-*-*-*-*-*-*
*-*-*-*-*-**-*-*-*-*-*-*-*-*-**-*-*-*-*-*--*-*-*-**-*-*-*-*-*-*-*-*-**-*-*-*-*-*
*-*-*-**-*-*-*-*-*-**-*-*-*-*-*-**-*-*-*--*-*-**-*-*-*-*-*-**-*-*-*-*-*-**-*-*-*
*-*-**-*-*-*-*-**-*-*-*-**-*-*-*-*-**-*-*--**-*-*-*-*-**-*-*-*-**-*-*-*-*-**-*-*
*-*-**-*-*-**-*-*-*-**-*-*-**-*-*-*-**-*--**-*-*-*-**-*-*-**-*-*-*-**-*-*-**-*-*
*-**-*-*-**-*-*-**-*-*-**-*-*-**-*-*-**-*-*-*-*-**-*-*-**-*-*-**-*-*-**-*-*-**-*
*-**-*-*-**-*-**-*-**-*-*-**-*-**-*-**-*--**-*-**-*-**-*-*-**-*-**-*-**-*-*-**-*
*-**-*-**-*-**-*-**-*-**-*-**-*-**-*-**-*-*-*-**-*-**-*-**-*-**-*-**-*-**-*-**-*
*-**-*-**-**-*-**-*-**-**-*-**-*-**-*-**-*-*-**-*-**-*-**-**-*-**-*-**-**-*-**-*
*-**-**-*-**-**-*-**-**-*-**-**-*-**-**-*-*-**-*-**-**-*-**-**-*-**-**-*-**-**-*
*-**-**-**-*-**-**-**-*-**-**-**-*-**-**-*-**-*-**-**-**-*-**-**-**-*-**-**-**-*
*-**-**-**-**-**-**-*-**-**-**-**-**-**-*-*-**-**-**-**-**-*-**-**-**-**-**-**-*
*-**-**-**-**-**-**-**-**-**-**-**-**-**-*-**-**-**-**-**-**-**-**-**-**-**-**-*
**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**-**
**-**-**-**-**-***-**-**-**-**-***-**-**-*-**-***-**-**-**-**-***-**-**-**-**-**
**-**-**-***-**-**-***-**-**-***-**-**-**-**-**-***-**-**-***-**-**-***-**-**-**
**-**-***-**-***-**-***-**-***-**-***-**-*-***-**-***-**-***-**-***-**-***-**-**
**-**-***-***-**-***-***-**-***-***-**-**-**-***-***-**-***-***-**-***-***-**-**
**-***-***-**-***-***-***-***-**-***-***-**-***-**-***-***-***-***-**-***-***-**
**-***-***-***-***-***-***-***-***-***-**-***-***-***-***-***-***-***-***-***-**
**-***-****-***-***-***-***-****-***-***-**-***-****-***-***-***-***-****-***-**
**-****-***-****-***-***-****-***-****-**-****-***-****-***-***-****-***-****-**
**-****-****-***-****-****-****-***-****-***-***-****-****-****-***-****-****-**
**-****-****-****-****-****-****-****-***-****-****-****-****-****-****-****-***
***-****-****-*****-****-****-*****-****-***-*****-****-****-*****-****-****-***
***-*****-****-*****-*****-****-*****-****-*****-****-*****-*****-****-*****-***
***-*****-*****-******-*****-*****-*****-****-*****-*****-******-*****-*****-***
***-******-******-*****-******-******-****-******-******-*****-******-******-***
****-******-******-******-*******-******-*****-*******-******-******-******-****
****-*******-*******-*******-*******-******-*******-*******-*******-*******-****
****-********-********-********-********-*******-********-********-********-****
*****-*********-*********-*********-********-*********-*********-*********-*****
******-**********-***********-**********-*********-***********-**********-******
*******-************-************-************-************-************-*******
********-***************-***************-**************-***************-********
**********-*******************-******************-*******************-**********
*************-**************************-*************************-*************
********************-**************************************-********************
****************************************-***************************************
********************************************************************************

Note that I couldn't get any of them to produce truly even distribution so I've added a new answer.

-1

This function will generate an even mixture of any number of lists, without relying on the expensive sort

from typing import Any, Iterable, List

def evenly_mix(*lists: List[Any]) -> Iterable[Any]:
    lens = [len(b) for b in lists]
    m = max(lens)
    cnts, psums = [[0 for _ in lists] for _ in [0, 0]]
    for i in range(m):
        for j, b in enumerate(lists):
            psums[j] += 1
            if psums[j] * lens[j] >= (cnts[j] + 1) * m:
                yield b[cnts[j]]
                cnts[j] += 1

The version below can run into numeric precision problem with divison.

from typing import Any, Iterable, List

def evenly_mix(*lists: List[Any]) -> Iterable[Any]:
    m = max(len(b) for b in lists)
    deltas = [len(b) / m for b in lists]
    cnts, psums = [[0 for _ in lists] for _ in [0, 0]]
    for i in range(m):
        for j, b in enumerate(lists):
            psums[j] += deltas[j]
            if psums[j] >= cnts[j] + 1:
                yield b[cnts[j]]
                cnts[j] += 1
4
  • This has a bug: print(list(evenly_mix(list("AAAAAAAAAAA"), list("BBB"))).count("B")) -> 2. Where it should be 3.
    – ideasman42
    Commented May 23 at 0:28
  • This is due to limitation of numeric precision in python. The code can be fixed by manipulating fractions with integers directly.
    – John Jiang
    Commented May 26 at 2:59
  • in that case the answer should be updated, otherwise this answer may be used, introducing bugs into software.
    – ideasman42
    Commented May 26 at 4:27
  • I have updated the answer and tried to mention it in my previous comment but somehow it was not saved.
    – John Jiang
    Commented May 26 at 5:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.