如何检查嵌套列表树中的所有元素是否相同？

Question

我正在尝试创建一个名为allsametree(tree)的函数，它接受一个列表tree作为输入，并返回TRUE或FALSE，如果列表中的所有元素在数值上都相同。到目前为止，我有以下函数：

def allsametree(tree):
    if not type(tree) == list:
        return tree
    if type(tree) is list:
        final_lst = []
        for item in tree:
            final_lst.append(allsametree(item))
        return final_lst[1:] == final_lst[:-1]

虽然这个函数在大部分情况下都可以正常运行，但在评估allsametree([1, [[[[[2]]]]]])时会遇到问题。

您有什么提示或者其他解决此问题的方法吗？

- Albert Lee

Answer 1

你可以将列表递归转换为一组项目，并返回true，如果整体集合的长度为1：

def allsametree(tree):
    def to_set(tree):
        if isinstance(tree, list):
            return {item for obj in tree for item in to_set(obj)}
        return {tree}
    return len(to_set(tree)) == 1

- blhsing

---

尽管这解决了上述的情况，但我也担心评估空列表[]。这种方法会忽略空列表并返回false，因为len([])为0而不是1。无论如何，我仍然感谢你的帮助。 - Albert Lee

OP没有指定在空列表中返回什么，但从“所有项目都相同”的措辞中，我解释为需要列表中至少有一个元素才能被视为具有相同的项。否则，很容易将“== 1”更改为“<= 1”。 - blhsing

感谢您的澄清，这确实很有道理！ - Albert Lee

Answer 2

另一种方法是将其拆分为两个操作：展平和检查所有值是否相同。

展平将嵌套可迭代对象转换为单个维度的对象。因此，[1，[[[[[2]]]]]] 变成了 [1,2]。

然后读取第一个值并循环遍历其余部分以检查它们是否与第一个值相同。

以下是代码：

from collections.abc import Iterable

def flatten(iterable):
    for i in iterable:
        if isinstance(i, Iterable):
            yield from flatten(i)
        else:
            yield i


def allsametree(tree):
    flat = flatten(tree)
    iterator = iter(flat)
    try:
        first = next(iterator)
    except StopIteration:
        return True
    return all(first == rest for rest in iterator)

这将适用于任何可迭代对象，而不仅仅是列表，并且由于它使用惰性求值，它将在找到两个不相等的值时停止。这可以避免您做不必要的工作。它还避免了在每个递归调用中构建的临时集合（列表、集等）的实例化。

这里有一些测试输入（链接）。

- Paul Rooney

---

这非常有见地，我没有想到过。谢谢！ - Albert Lee