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

[Wesley]

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).

Any comments will be appreciated.
Thanks.
Wesley

 

[Asaf Las]

Hi guys,
Here is one question related to algorithm.
Details here:

here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax andbx 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).

Any comments will be appreciated.

Thanks.

Wesley

if space O(1) is needed they don't have to be merged - list alike class keeping series as members returning a if i is odd and b if i is even would be enough. then constructing such sequence (or class instance) will be done in O(1) as well.

/Asaf

 

[Chris Angelico]

here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax andbx 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).

The two halves of the list are already sorted, yes? Then you don't
need a sort operation, just a zip.

def flip_list(lst):
offset = len(lst)//2
for i in range(offset):
yield lst
yield lst[i+offset]

start = ['a1','a2','a3','a4','b1','b2','b3','b4']
result = list(flip_list(start))
print(result)

Alternatively, you could arrange this as some kind of swap operation,
modifying the list in place, but I think the more Pythonic way will be
to create a new list. Note that, with the function defined as I have
above, you can iterate over the flipped list without actually
coalescing it in memory. That gives effective O(1) space, and it's
definitely O(n) time as it simply iterates over the whole list once.

ChrisA

 

[Oscar Benjamin]

Hi guys,
Here is one question related to algorithm.
Details here:

here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax andbx 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).

Do you mean that you have a list and you want to rearrange the
elements in-place without creating a new list?


Oscar

 

[Oscar Benjamin]

Please reply to the list rather than directly to me so that other
people can see the answer to my question and offer you help.

Yes

Okay so if you're going to do it with O(1) space then it's going to
have to be done with a whole bunch of swaps. Have a think with pen and
paper about how you could do a sequence of swaps that would rearrange
the order to the one that you want (it's actually a harder problem
than it looks at first glance). This is an example of what is known as
"transposition" and much information is available about algorithms for
doing this in-place:
http://en.wikipedia.org/wiki/In-place_matrix_transposition


Oscar

 

[Ni Wesley]

Yes, with no new list, otherwise, space won't to be O(1)

Wesley

 

[Roy Smith]

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))

 

[Oscar Benjamin]

Please don't top-post.

Yes, with no new list, otherwise, space won't to be O(1)

Did you read the link I posted:

Oscar

 

[Steven D'Aprano]

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).

Time complexity O(n) implies that you can iterate over the list at most a
constant number of times. Space complexity O(1) implies that you can only
use a small, constant amount of extra space, which means that you have to
modify the input sequence in place.

This is a kind of shuffle. Imagine you pull out all the spades â™  and
hearts ♡ from a deck of cards, and sort them individually:

cards = ['Aâ™ ', '2â™ ', '3â™ ', '4â™ ', ... 'Kâ™ ',
'A♡', '2♡', '3♡', '4♡', ... 'K♡']

You want to move the cards so that you end up with the spades and hearts
interleaved:

cards = ['A♠', 'A♡', '2♠', '2♡', '3♠', '3♡',
'4♠', '4♡', ... 'K♠', 'K♡']


This is called a "riffle shuffle" or "Faro shuffle", and there are two
kinds, an in-shuffle and an out-shuffle, which differ in which card ends
up on top. The obvious way to do it is to split the deck down the middle
into two sets of cards, then riffle them together, one card from the left
hand following by one card from the right (or visa versa):

left = cards[:len(cards)//2]
right = cards[len(cards)//2:]
cards = []
for l, r in zip(left, right):
cards.append(l)
cards.append(r)


but this doesn't use constant space, since it uses extra space
proportional to N. Since this sounds like homework, I'm not going to tell
you how to do this using only constant space, but it may help if you
actually sit down with a set of cards, lay them out in order, and see how
you might do it by hand.

 

[Steven D'Aprano]

Is this a homework problem?

and then (paraphrasing):

working code that solves the problem

/headdesk

 

[Roy Smith]

and then (paraphrasing):


/headdesk

I gave him the benefit of the doubt.

Also, as I look at my solution, I realize it doesn't really meet the
O(1) space requirement. Understanding why is left as an exercise for
the reader

 

[Wesley]

在 2014å¹´2月9日星期日UTC+8下åˆ11æ—¶48分17秒，Oscar Benjamin写é“：

Please don't top-post.




Did you read the link I posted:



Oscar

Sorry getting a network problem these two days.
I am reading

 

[Wesley]

The two halves of the list are already sorted, yes?

[Wesley] No, not sorted yet..

 

[Wesley]

[Wesley] This is not homework
And actually I am new to algorithm, so you guys can feel free to say anything you want

 

[Dave Angel]

The two halves of the list are already sorted, yes?

[Wesley] No, not sorted yet..

Then supply some example lists and show the result you want. So
far, your description is thoroughly ambiguous.

 

[Sturla Molden]

[Wesley] This is not homework
And actually I am new to algorithm, so you guys can feel free to say anything you want

In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.

 

[Chris Angelico]

[Wesley] This is not homework
And actually I am new to algorithm, so you guys can feel free to say anything you want

In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.

That's assuming it really is a sort operation. The problem description
isn't entirely clear on this point, but if it's actually a zip, then
it can definitely be done in O(n).

ChrisA

 

[Sturla Molden]

That's assuming it really is a sort operation. The problem description
isn't entirely clear on this point, but if it's actually a zip, then
it can definitely be done in O(n).

Ah, I didn't read it carefully enough.

Granted, a zip can be done in O(n) time and O(1) memory using a generator,
which by the way is what itertools.izip does.

Sturla

 

[Chris Angelico]

Ah, I didn't read it carefully enough.

Granted, a zip can be done in O(n) time and O(1) memory using a generator,
which by the way is what itertools.izip does.

Right. I poked around in itertools but nothing was quite what I was
after, so I ended up writing my own generator. But it's still a zip
operation, and as such, is just a variant form of iterating over the
original list. All I do is follow a pattern other than the Red King's
"Begin at the beginning, go on till you come to the end, then raise
StopIteration" (or words to that effect).

 

[Chris Angelico]

Something like

mylist[:] = reorder_generator(mylist)

won't work because the generator would need to access the data
non-sequentially (it would need to read elements after they were
overwritten).

This would have O(1) space and O(n) time. It's absolutely perfect...
except that you now don't technically have a list any more:

mylist = reorder_generator(mylist)

You can iterate over it, but can't index it. But hey, it complies with
the space/time requirements!

ChrisA