Move odd and even numbers in list to odd and even positions

Question

I have a list with an equal number of odd and even integers. The goal is to modify the list to have odd integers at odd indices and even integers at the even indices.

Here is my approach:

I find out the numbers at even indexes and odd indexes. Then find out odd numbers at even indexes and even numbers at odd indexes. Finally swap the misplaced numbers.

x = [3, 2, 5, 6, 4, 7, 8, 9, 10, 11]
even_pos = []
odd_pos = []
for i in range(len(x)):
    if x[i] % 2 == 0:
        even_pos.append(i)
    else:
        odd_pos.append(i)

even_pos_with_odd = []
odd_pos_with_even = []

for j in range(len(even_pos)):
    if even_pos[j] % 2 != 0:
        even_pos_with_odd.append(j)
    if odd_pos[j] % 2 == 0:
        odd_pos_with_even.append(j)

for n in range(len(even_pos_with_odd)):
    temp =  x[odd_pos[odd_pos_with_even[n]]]
    x[odd_pos[odd_pos_with_even[n]]] = x[even_pos[even_pos_with_odd[n]]]
    x[even_pos[even_pos_with_odd[n]]] = temp

I am not very happy with the solution though it works. Is there any better efficient solution to my problem? My aim was to make x[] like [2, 3, 6, 5, 4, 7, 8, 9, 10, 11] possibly sorted in the same odd-even format.

Answer 1

To move all even items to even indices and all odd items to odd indices inplace in O(n**2) time:

def fix_odd_even_indices(lst):
    for i in range(len(lst)):
        j = i
        while i & 1 != lst[i] & 1: # element is in the wrong place
            j += 1
            lst[i], lst[j] = lst[j], lst[i] # swap

The code may raise IndexError if the number of odds and evens is unequal.

Example:

lst = [3, 2, 5, 6, 4, 7, 8, 9, 10, 11]
fix_odd_even_indices(lst)
print(lst)
# -> [2, 3, 6, 5, 4, 7, 8, 9, 10, 11]

---

Here's a linear solution that returns a copy:

def fixed_odd_even_indices(seq):
    L = [None]*len(seq)
    L[1::2] = [x for x in seq if x & 1] # odd
    L[::2] = [x for x in seq if not x & 1] # even
    return L

Example:

print(fixed_odd_even_indices([3, 2, 5, 6, 4, 7, 8, 9, 10, 11]))
# -> [2, 3, 6, 5, 4, 7, 8, 9, 10, 11]

Here's a linear single-pass solution that returns a copy (it is probably slower than the previous solution):

def fixed_odd_even_indices(iterable):
    odds, evens = [], []
    for x in iterable:
        (odds if x & 1 else evens).append(x)
    return [x for pair in zip(evens, odds) for x in pair]

Example:

L = fixed_odd_even_indices(map(int, sys.stdin)) # input one integer per line

Answer 2

def odd_even(x):
    odds = sorted(filter(lambda n: n % 2 == 1, x))
    evens = sorted(filter(lambda n: n % 2 == 0, x))
    pairList = zip(odds, evens)
    return [n for t in pairList for n in t]

Answer 3

itertools.count version of the solution by @MartijnPieters

>>> from itertools import count
>>> x = [3, 2, 5, 6, 4, 7, 8, 9, 10, 11]
>>> def odd_even_sieve(x):
        output = x[:]
        a, b = count(0, 2), count(1, 2)
        for value in x:
            output[next(a if value % 2 == 0 else b)] = value
        return output

>>> odd_even_sieve(x)
[2, 3, 6, 5, 4, 7, 8, 9, 10, 11]

Answer 4

Though you have chosen your answer, but I'd like to submit my way. Hope you may like it.

# Using python  2.7

First_list = [1,3,5,7,2,4,6,8]   #equal no. of even and odd numbers

temp_odd = [x for x in First_list if x%2 ==1]
temp_even = [x for x in First_list if x%2 ==0]

First_list[0::2] = temp_even    # as we know,0 is even index,followed by 2,4...
First_list[1::2] = temp_odd     # similarly starting with index 1, odd indices 
                                # are 3,5 ...
                                # we can write sorted(temp_odd) like that

print First_list

Answer 5

If someone is looking for a function to flip the odd and even indices of an array, he/she can use this one:

import numpy as np
def flip(x):
        '''x must be an array'''
        flipped=[]
        for i in range(int(len(x)/2)):
                flipped.append(x[(i+1)*2-1])
                flipped.append(x[i*2])
        flipped=np.array(flipped)
        return flipped
>>> print(x)
[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19]
>>> print(flip(x))
[ 1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14 17 16 19 18]