Home Original page

Sort one sequence by O(n) in time and O(1) in space

Roy Smith roy at panix.com
Sun Feb 9 10:05:02 EST 2014 
In article <ae372652-0f1c-4d79-82db-a522eb592579 at googlegroups.com>,
 Wesley <nispray at gmail.com> wrote:

> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always 
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with 
> time complexity as O(n) and space as O(1).

Is this a homework problem?

It sounds like what you want to do is split the list into two halves, then shuffle them.  Using
itertools let's you do these operations without making copies of the data.  

Something like:

--------------------------------------------------
from itertools import islice, izip

def cut_and_shuffle(input):
    n = len(input)
    if n % 2:
        raise ValueError("input length must be even")
    split = n/2
    print "split =", split
    first_half = islice(input, 0, split)
    second_half = islice(input, split, n)
    for a, b in izip(first_half, second_half):
        yield a
        yield b

l = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4']
print list(cut_and_shuffle(l))
--------------------------------------------------

$ python shuffle.py
split = 4
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']
More information about the Python-list mailing list