CODEWITHSUNDEEP
pythonoverflow
zzzbbx
zzzbbx

Reputation: 10131

Wrap-around detection

Suppose you have a list of values in increasing order, except that at some point they wrap-wround

2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7, ...

Knowing that the period is 2^n, for some value of n, is there any built-in function, or a fast way to rearrange the values above so that all numbers are in increasing order (assuming the numbers are such that it is possible)?

Upvotes: 0

Views: 442

Answers (4)

Leovt
Leovt

Reputation: 313

An expected output would help in understanding your question. I have guessed a different desired solution than others. Maybe someone else can find a more concise solution for this interpretation.

The output would be 2, 4, 6, 9, 12, 15, 34, 62, 65, 68, 69, ... i.e. all values starting from -2 are shifted up by 64

First I guess the period size 64. This could be done e.g. by looking at the most negative difference of neighbour elements and rounding up to a power of 2. This might not be possible if you dont have all values available in the beginning. 

period = 64

def unwrap(seq):
    it = iter(seq)
    try:
        lastitem = next(it)
    except StopIteration:
        return
    yield lastitem
    shift = 0
    for item in it: 
        if item < lastitem:
            shift += period
        yield item + shift
        lastitem = item

If you need a list and not a generator you can use

result = list(unwrap(original_list))

Upvotes: 2

nate_weldon
nate_weldon

Reputation: 2349

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()

Upvotes: 0

lunixbochs
lunixbochs

Reputation: 22415

If you want all of the values to be in increasing order, that's a sort:

>>> sorted([2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7])
[-2, 1, 2, 4, 5, 6, 7, 9, 12, 15, 34]

Are you trying to optimize the sort based on the knowledge it's consecutive numbers wrapping at intervals, or asking a different question?

Upvotes: 0

liori
liori

Reputation: 42277

list.sort() might be fast enough. In CPython it is implemented using Timsort, which should handle cases like your in a better-than-average way (the first stage is looking for already sorted runs of numbers exactly like in your case).

Upvotes: 5

Related Questions