Recursively rearrange a sequence of integers from even to odd

Question

This is a practice problem that I've been trying to solve for a while:

Write a recursive Python function that rearranges a sequence of integer values so that all the even values appear before all the odd values.

What I have:

def arrange(x):
    even = ''
    odd = ''
    y = str(x)
    if y == '':
        return y
    elif int(y[0]) % 2 == 0:
        even += y[0]
        if y[1:] != '':
            arrange(int(y[1:]))
    else:
        odd += y[0]
        if y[1:] != '':
            arrange(int(y[1:]))
    final = int(even + odd)

After running the visualizer, I think the problem in the code lies within the fact that even and odd are reset everytime. Though, I need it all to be in one function. Any advice?

EDIT: Completed in case anyone wanted to use the same practice problem -

even = []
odd = []

def arrange(x):
    y = str(x)
    if y == '':
        return y
    elif int(y[0]) % 2 == 0:
        even.append(y[0])
        if y[1:] != '':
            arrange(int(y[1:]))
    else:
        odd.append(y[0])
        if y[1:] != '':
            arrange(int(y[1:]))

def complete(x):
    evens = ''
    odds = ''
    arrange(x)
    for i in even:
        evens += i
    for i in odd:
        odds += i
    return int(evens + odds)

Answer 1

Here's a simple solution. For a given index ind recursively apply func for the list, ind ownwards, followed by checking whether the value at ind is even or odd. If odd, just move that value to the end of the list.

When the recursion starts to unwrap, it will begin rearrangement from the end of list and as the stack unwinds, the pervious elements of the list would start to fall in the right places.

def func(lst, ind=0):
    if ind < len(lst):
        func(lst, ind+1)
        if lst[ind] % 2 != 0:
            lst.append(lst.pop(ind))
    return lst

print func([3,4,6,2,1])

Answer 2

Here is an efficient, short way to do this (not recursive however).

A string in Python is an iterable, so there actually is no need to keep taking substrings of the original input. Instead, you could filter out the odd and even digits and later concatenate them.

def splitEvenOdd(x):
    even = [e for e in x if int(e)%2 == 0]
    odd = [o for o in x if int(o)%2 == 0]
    even = "".join(even)
    odd = "".join(odd)
    return even + odd

Answer 3

I wasn't sure what your desired output was, or if you wanted it to recurse and keep the structure/order. Here's a swiss army knife.

from pprint import pprint


def even_before_odd(values, keep_structure=False, sort=False):
    evens, odds = even_odd(values, keep_structure, sort)
    return evens + odds

def even_odd(values, keep_structure=False, sort=False):
    evens = []
    odds = []

    for value in values:
        if isinstance(value, list):
            _evens, _odds = even_odd(value, keep_structure, sort)
            if keep_structure:
                # This will insert a sub array 
                evens.append(_evens)
                odds.append(_odds)
            else:
                # This will append them to the list
                evens += _evens
                odds += _odds
            continue
        if value % 2 == 0:
            evens.append(value)
        else:
            odds.append(value)

    if sort:
        evens = sorted(evens)
        odds = sorted(odds)

    return evens, odds

values = []
for x in range(0,10):
    values.append(list(range(0,10)))

result = even_before_odd(values, False, True)
print "result 1:", ",".join(map(str, result))

result = even_before_odd(values, False, False)
print "result 2:", ",".join(map(str, result))

print "result 3:"
result = even_before_odd(values, True, True)
pprint(result)

Output:

result 1: 0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,4,4,6,6,6,6,6,6,6,6,6,6,8,8,8,8,8,8,8,8,8,8,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,3,3,3,3,5,5,5,5,5,5,5,5,5,5,7,7,7,7,7,7,7,7,7,7,9,9,9,9,9,9,9,9,9,9
result 2: 0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,0,2,4,6,8,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9
result 3
[[0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [0, 2, 4, 6, 8],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9],
 [1, 3, 5, 7, 9]]

Answer 4

I have a different solution, it isn't very efficient if you're working with larger lists*, but I guess for an assignment it's fine:

def evenBeforeOdd(x):
    if not x:
        return []
    if x[0] % 2 == 0: #even
        return [x[0]] + evenBeforeOdd(x[1:])
    else:
        return evenBeforeOdd(x[1:]) + [x[0]]

*: If I remember correctly, adding lists together is pricy (O(n), plus the slicing, which is O(1) in our case, I think), which it needs to do for each item of the list, so the whole thing should be O(n^2). Also it's not very memory efficient, since it must create new lists all the time.

If I actually wanted to solve the problem without the recursivity requirement, it'd simply be something like this:

sorted(myList, key=lambda x: x%2!=0)

Answer 5

Disclaimer

I do not know any python. I am answering this question as much as a learning exercise for me as the problem is an exercise for you.

I have not checked this answer for syntax errors.

---

I think your hunch that the problem is due to even and odd being reset on each call is correct - you need to pass them in to rearrange. Here is my attempt:

def arrange(x, evenInput, oddInput):
    even = str(evenInput)
    odd = str(oddInput)
    y = str(x)
    if y == '':
        return y
    elif int(y[0]) % 2 == 0:
        even += y[0]
        if y[1:] != '':
            arrange(int(y[1:]), even, odd)
    else:
        odd += y[0]
        if y[1:] != '':
            arrange(int(y[1:]), even, odd)
    final = int(even + odd)