Recursively dividing up a list, based on the endpoints

user_11634814 0
Viewed 820

Here is what I am trying to do. Take the list:

list1 = [0,2]

This list has start point 0 and end point 2. Now, if we were to take the midpoint of this list, the list would become:

list1 = [0,1,2]

Now, if we were to recursively split up the list again (take the midpoints of the midpoints), the list would becomes:

list1 = [0,.5,1,1.5,2]

I need a function that will generate lists like this, preferably by keeping track of a variable. So, for instance, let's say there is a variable, n, that keeps track of something. When n = 1, the list might be [0,1,2] and when n = 2, the list might be [0,.5,1,1.5,2], and I am going to increment the value of to keep track of how many times I have divided up the list.

I know you need to use recursion for this, but I'm not sure how to implement it.

Should be something like this:

def recursive(list1,a,b,n):
  """list 1 is a list of values, a and b are the start
     and end points of the list, and n is an int representing
     how many times the list needs to be divided"""
   int mid = len(list1)//2
 stuff

Could someone help me write this function? Not for homework, part of a project I'm working on that involves using mesh analysis to divide up rectangle into parts.

This is what I have so far:

def recursive(a,b,list1,n):
  w = b - a
  mid = a +  w / 2
  left = list1[0:mid]
  right = list1[mid:len(list1)-1]
  return recursive(a,mid,list1,n) + mid + recursive(mid,b,list1,n)

but I'm not sure how to incorporate n into here.

NOTE: The list1 would initially be [a,b] - I would just manually enter that but I'm sure there's a better way to do it.

recursion list function arrays python
5 Answers

You've generated some interesting answers. Here are two more.

My first uses an iterator to avoid slicing the list and is recursive because that seems like the most natural formulation.

def list_split(orig, n):
    if not n:
        return orig
    else:
        li = iter(orig)
        this = next(li)
        result = [this]
        for nxt in li:
            result.extend([(this+nxt)/2, nxt])
            this = nxt
        return list_split(result, n-1)

for i in range(6):
    print(i, list_split([0, 2], i))

This prints

0 [0, 2]
1 [0, 1.0, 2]
2 [0, 0.5, 1.0, 1.5, 2]
3 [0, 0.25, 0.5, 0.75, 1.0, 1.25, 1.5, 1.75, 2]
4 [0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, 1.0, 1.125, 1.25, 1.375, 1.5, 1.625, 1.75, 1.875, 2]
5 [0, 0.0625, 0.125, 0.1875, 0.25, 0.3125, 0.375, 0.4375, 0.5, 0.5625, 0.625, 0.6875, 0.75, 0.8125, 0.875, 0.9375, 1.0, 1.0625, 1.125, 1.1875, 1.25, 1.3125, 1.375, 1.4375, 1.5, 1.5625, 1.625, 1.6875, 1.75, 1.8125, 1.875, 1.9375, 2]

My second is based on the observation that recursion isn't necessary if you always start from two elements. Suppose those elements are mn and mx. After N applications of the split operation you will have 2^N+1 elements in it, so the numerical distance between the elements will be (mx-mn)/(2**N).

Given this information it should therefore be possible to deterministically compute the elements of the array, or even easier to use numpy.linspace like this:

def grid(emin, emax, N):
    return numpy.linspace(emin, emax, 2**N+1)

This appears to give the same answers, and will probably serve you best in the long run.

user_1460730

You can use some arithmetic and slicing to figure out the size of the result, and fill it efficiently with values.

While not required, you can implement a recursive call by wrapping this functionality in a simple helper function, which checks what iteration of splitting you are on, and splits the list further if you are not at your limit.

def expand(a):
    """
    expands a list based on average values between every two values
    """
    o = [0] * ((len(a) * 2) - 1)
    o[::2] = a
    o[1::2] = [(x+y)/2 for x, y in zip(a, a[1:])]
    return o

def rec_expand(a, n):
    if n == 0:
        return a
    else:
        return rec_expand(expand(a), n-1)

In action

>>> rec_expand([0, 2], 2)
[0, 0.5, 1.0, 1.5, 2]

>>> rec_expand([0, 2], 4)
[0,
 0.125,
 0.25,
 0.375,
 0.5,
 0.625,
 0.75,
 0.875,
 1.0,
 1.125,
 1.25,
 1.375,
 1.5,
 1.625,
 1.75,
 1.875,
 2]
user_34832030

You could do this with a for loop

import numpy as np

def add_midpoints(orig_list, n):
    for i in range(n):
        new_list = []
        for j in range(len(orig_list)-1):
            new_list.append(np.mean(orig_list[j:(j+2)]))

        orig_list = orig_list + new_list
        orig_list.sort()

    return orig_list

add_midpoints([0,2],1)
[0, 1.0, 2]
add_midpoints([0,2],2)
[0, 0.5, 1.0, 1.5, 2]
add_midpoints([0,2],3)
[0, 0.25, 0.5, 0.75, 1.0, 1.25, 1.5, 1.75, 2]
user_50491710

You can also do this totally non-recursively and without looping. What we're doing here is just making a binary scale between two numbers like on most Imperial system rulers.

def binary_scale(start, stop, level):
    length = stop - start
    scale = 2 ** level
    return [start + i * length / scale for i in range(scale + 1)]

In use:

>>> binary_scale(0, 10, 0)
[0.0, 10.0]
>>> binary_scale(0, 10, 2)
[0.0, 2.5, 5.0, 7.5, 10.0]
>>> binary_scale(10, 0, 1)
[10.0, 5.0, 0.0]
user_108633270

Fun with anti-patterns:

def expand(a, n):
    for _ in range(n):

        a[:-1] = sum(([a[i], (a[i] + a[i + 1]) / 2] for i in range(len(a) - 1)), [])

    return a

print(expand([0, 2], 2))

OUTPUT

% python3 test.py
[0, 0.5, 1.0, 1.5, 2]
%
user_57712690
Related