How do I separate a list into left and right sides using divide and conquer?

user_14546577 0
Viewed 175

I am trying to continually separate a list into left and right sides until no more half lists can be made and print them each time. Also I try to choose left or right side based on even or odd iterations.

Code:

low = 0
high = n
i=0
a = len(L1)
b = len(L2)
while a > 0 and b>0:
    
    mid = (low + high)// 2

    if i%2==0:
        print(L[low:mid])
        low = mid + 1
        print(L[mid:high])
    else:
        print(L[low:mid])
        high = mid - 1
        print(L[low:high])
        print(L[mid:high])
    i=i+1

L = [1, 2, 3, 4, 5]
# should print:
 [1, 2, 3]
 [4, 5]
 [1, 2]
 [3]
 [4]
 [5]

Any help please

divide-and-conquer python-3.x python
1 Answers

The natural way to do this is to put your dividing and printing operations inside a function, so that you can call that function recursively on the sublists, until you reach lists of length 1:

def divide(L):
    """Recursively divide list L and print the sublists at each level."""
    
    if len(L) <= 1:  # base case: nothing left to do
        return()
    
    mid = (len(L) + 1) // 2  # if odd length, left sublist will be longer 
    L_left = L[:mid]  # left sublist
    L_right = L[mid:]  # right sublist
    print(L_left)
    print(L_right)
    
    # recursive function calls to further divide the sublists
    divide(L_left)  
    divide(L_right)
    
    return()
    
L = [1, 2, 3, 4, 5]
divide(L)

[1, 2, 3]
[4, 5]
[1, 2]
[3]
[1]
[2]
[4]
[5]

Note that this does not address your idea

to choose left or right side based on even or odd iterations

because I'm not sure what you mean by that.

user_130141720
Related