Рекурсивное разделение списка на основе конечных точек

Question

Вот что я пытаюсь сделать.Возьмите список:

list1 = [0,2]

Этот список имеет начальную точку 0 и конечную точку 2. Теперь, если бы мы взяли среднюю точку этого списка, список стал бы:

list1 = [0,1,2]

Теперь, если бы мы рекурсивно разделяли список снова (взяли средние точки средних точек), список стал бы следующим:

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

Мне нужна функция, которая будет генерировать списки, подобные этому, предпочтительно с сохранениемдорожка переменной.Например, предположим, что есть переменная n, которая отслеживает что-то.Когда n = 1, список может быть [0,1,2], а когда n = 2, список может быть [0, .5,1,1.5,2], и я собираюсь увеличить значение, чтобы сохранитьотслеживать, сколько раз я делил список.

Я знаю, что для этого нужно использовать рекурсию, но я не уверен, как ее реализовать.

Должно быть что-то вроде этого:

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

Может ли кто-нибудь помочь мне написать эту функцию?Не для домашней работы, часть проекта, над которым я работаю, который включает использование анализа сетки для разделения прямоугольника на части.

Это то, что у меня есть:

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)

, но яя не уверен, как включить n сюда.

ПРИМЕЧАНИЕ. Первоначально list1 был бы [a, b] - я просто ввел бы это вручную, но я уверен, что есть лучший способ сделать это.

Answer 1

Вы сгенерировали несколько интересных ответов. Вот еще два.

Мой первый использует итератор, чтобы избежать разрезание списка и является рекурсивным, потому что это кажется наиболее естественной формулировкой.

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))

Это печатает

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]

Мое второе основано на наблюдении, что рекурсия не нужна, если вы всегда начинаете с двух элементов. Предположим, что эти элементы mn и mx. После применения N операции разделения у вас будет 2^N+1 элементов, поэтому числовое расстояние между элементами будет (mx-mn)/(2**N).

Учитывая эту информацию, следовательно, должна быть возможность детерминистически вычислить элементы массива, или еще проще использовать numpy.linspace следующим образом:

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

Похоже, что это дает те же ответы, и, вероятно, послужит вам лучше всего в долгосрочной перспективе.

Answer 2

Вы можете использовать некоторую арифметику и нарезку, чтобы выяснить размер результата и эффективно заполнить его значениями.

Хотя это и не требуется, вы можете реализовать рекурсивный вызов, обернув эту функцию в простую вспомогательную функцию, которая проверяет, на какой итерации разделения вы находитесь, и разбивает список дальше, если вы не ограничены.

---

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)

---

В действии

>>> 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]

Answer 3

Веселье с анти-паттернами:

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]
%

Answer 4

Вы также можете сделать это абсолютно не рекурсивно и без циклического повторения. Здесь мы просто делаем двоичную шкалу между двумя числами, как на большинстве правителей Имперской системы.

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

Используется:

>>> 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]

Answer 5

Вы можете сделать это с помощью цикла for

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]