Sort one sequence by O(n) in time and O(1) in space
oscar.j.benjamin at gmail.com
Mon Feb 10 16:45:08 CET 2014
On 10 February 2014 15:03, Sturla Molden <sturla.molden at gmail.com> wrote:
> Chris Angelico <rosuav at gmail.com> wrote:
>> 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.
Yes but turning the generator into a list takes O(N) storage (for the
new list!). The OP wants to rearrange a list in-place.
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
The way to do this is to find the cycles of data movement i.e. the
sets of indices for which a permutation occurs. If you know the size
of the input then you can find these once and hard-code them.
Otherwise you need an algorithm that finds each cycle exactly once
using O(1) storage which is definitely not trivial.
You can see the top-level code that fftw uses for this here (I think
this code is very hard to follow without prior experience of their
code base - I certainly don't understand it):
I'm not even sure if that really is O(1) storage though: it may be
something like O(MN/gcd(M, N)).
This page describes the general problem
and mentions the existence of "more complicated" algorithms that can
use O(N+M) or O(log(MN)) storage.
So I don't think an O(1) storage O(N) operations solution exists for
the general M*N case although it may be possible for the
specialisation to 2*M. (I haven't tried this but if you're interested
see what cycles come up for different input sizes and whether there's
a pattern that can be predicted using O(1) storage).
More information about the Python-list