基于端点递归地划分列表

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] - 我只是手动输入，但我相信有更好的方法来做到这一点。

- Evan

---

你自己有尝试过写这个吗？ - Devesh Kumar Singh

是的，我正在编辑它，马上就好，请稍等。 - Evan

好的，已更新 - 我只是在尝试弄清楚如何主要地将n纳入其中，比如如何告诉它停止。 - Evan

你可以使用变量 n，一旦它达到该值，就使用 break 停止循环。 - MEdwin

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)

这似乎提供了相同的答案，并且在长期内可能对您最有帮助。

- holdenweb

---

有趣，我认为递归似乎是这个问题的解决方法，感谢您提供的简洁解决方案！ - Evan

很高兴。我很早就意识到，当Python代码易于阅读时，它也容易理解，因此我尽量保持简单，即使这需要更长的时间。 - holdenweb

在3.8中，我们将能够通过PEP 572编写result = [this := next(li)]，而不是this = next(li); result = [this]。 - holdenweb

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]

- user3483203

---

我认为你递归的一个更有用的基本情况是 n == 0，在这种情况下，你应该返回 a。 - Kyle Parsons

噢，好的，很聪明，没有预料到那个路线！我看明白它是如何工作的，只需要递归的帮助函数，非常感谢！ - Evan

你不需要这个帮助函数，但它可以让递归的工作方式更清晰。 - user3483203

同意 - 对于初学者来说，看到递归控制逻辑和实际计算之间的区别通常是有帮助的。 - holdenweb

Answer 3

你可以使用 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]

- Kristofersen

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]

- Kyle Parsons

---

如果他们从列表 [0, 3, 1] 开始怎么办？我同意你可以一步完成所有操作，但这仅适用于 start > stop 的单个起始/停止值。尽管如此，这仍然是一个有用的答案。 - user3483203

你是什么意思，"不用循环"？[... for i in range(...)] 不就是一个循环吗？ - cdlane

根据发帖者的问题和示例代码，@user3483203 是使用案例。 - Kyle Parsons

@cdlane 虽然在底层实现上可能是一个循环，但列表推导式是一种更受欢迎的模式，通常也运行得更快。 - Kyle Parsons

如果你能看到 for，那么它就不是“在引擎盖下”的东西。像 map() 这样的东西就是“在引擎盖下”的循环。更喜欢的循环语法仍然是循环。更快的循环语法仍然是循环。 - cdlane

Answer 5

反模式的乐趣：

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

输出

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

- cdlane