Как мне проверить, все ли элементы дерева вложенных списков идентичны?

#python #python-3.x #recursion

#python #python-3.x #рекурсия

Вопрос:

Я пытаюсь создать функцию 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]]]]]])

Какие-либо советы или альтернативные способы решения этой проблемы?

Ответ №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

1. Хотя это касается случая, указанного выше, меня также беспокоит оценка пустых списков [] . Этот метод будет пропускать пустые списки и возвращать false, поскольку len([]) вместо 1 будет 0. Тем не менее, я ценю вашу помощь.

2. OP не указывает, что возвращать с пустым списком, но из формулировки «все элементы идентичны» я интерпретирую это как список, в котором должно быть что-то вообще, чтобы считаться имеющим идентичные элементы. В противном случае его легко изменить == 1 <= 1 .

3. Спасибо за разъяснения, и это, безусловно, имеет смысл!

Ответ №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)

Это будет работать для любых iterable , а не только для списков, и поскольку он использует отложенную оценку, он остановится, когда найдет два значения, которые не равны. Это избавляет вас от выполнения ненужной работы. Это также позволяет избежать создания временных коллекций (списков, наборов и т. Д.), Создаваемых при каждом рекурсивном вызове.

Вот несколько тестовых входных данных.