Блог

Я борюсь с упражнением в течение нескольких дней. Задан следующий вложенный список:

 [1, [5, 62, 6], 4, [99, [100, 200, 600, [1000, [2000]]]], [74, 41, 16], 7, [8], [[[400]]]]
  

И это тело функции:

 def find_element(liste, find, index = 0):
  

Мне нужно найти элемент во вложенном списке, и функция должна возвращать точный индекс найденного элемента, например [1,0] для 5 или [3, 1, 3, 1, 0] за 2000 год.
Функция должна быть рекурсивной.

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

Это мой код:

 def find_element(liste, find, index = 0):
    indexList = []

    if len(liste) == index:
        return indexList

    if liste[index] == find:
        indexList.append(index)
    else:
        if type(liste[index]) == list:
            indexList.extend(find_element(liste[index], find))
        if indexList:
            indexList.insert(0, index)
        else:
            indexList.extend(find_element(liste, find, index   1))

    return indexList
  

Я попробовал вторую функцию, которая возвращает false, когда список пуст, или условие if, если индекс равен 0, а список индексов пуст, но все, что я получил, это ошибка рекурсии или ошибка типа.

Ответ Ajax1234 работает, но если вам нужно что-то более простое, это может быть лучше:

 def find_idx(input_list, elem):
  for i in range(len(input_list)):
    if isinstance(input_list[i], list):
      result = find_idx(input_list[i], elem)
      if result:
        return [i]   result
    elif input_list[i] == elem:
        return [i]

  return False

input_list = [1, [5, 62, 6], 4, [99, [100, 200, 600, [1000, [2000]]]], [74, 41, 16], 7, [8], [[[400]]]]

print(find_idx(input_list, 2000))
# Output: [3, 1, 3, 1, 0]  

 
  

По сути, это DFS (https://en.wikipedia.org/wiki/Depth-first_search ). Если вы представляете свою структуру данных как дерево, записи вашего списка являются узлами, поскольку они сами могут содержать другие списки, точно так же, как узел в дереве может указывать на другие узлы. Волшебство заключается в возврате False , если ничего не было найдено в самом конце метода, но рекурсивный поиск по всем подспискам, прежде чем вы дойдете до этой точки. Кроме того, вы должны проверить, является ли ваша запись списка сама по себе списком, но это всего лишь аналогия с тем фактом, что в дереве могут быть узлы, которые указывают на другие узлы, и узлы, которые этого не делают (конечные узлы или простые старые числа в вашем случае).

Вы можете использовать рекурсию с генератором:

 def find_element(l, elem):
  def get_elem(d, c = []):
    for i, a in enumerate(d):
       if a == elem:
          yield c [i]
       elif isinstance(a, list):
          yield from get_elem(a, c [i])
  return False if not (r:=list(get_elem(l))) else r[0]

data = [1, [5, 62, 6], 4, [99, [100, 200, 600, [1000, [2000]]]], [74, 41, 16], 7, [8], [[[400]]]]
print(find_element(data, 2000))
  

Вывод:

 [3, 1, 3, 1, 0]
  

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

 def dfs(ls, r = []):
  if isinstance(ls, list):
    for (i, v) in enumerate(ls):
      yield from dfs(v, [*r, i])
  else:
    yield (r, ls)

def find_element(ls, q):
  for (k, v) in dfs(ls):
    if v == q:
      return k
  return None
  

 print(find_element(input, 5))
# [1, 0]

print(find_element(input, 2000))
# [3, 1, 3, 1, 0]

print(find_element(input, 999))
# None
  

Или вы могли бы исправить свою исходную программу, используя четвертый параметр, r = [] —

 def find_element(ls, q, i = 0, r = []):
  if i >= len(ls):
    return None
  elif isinstance(ls[i], list):
    return find_element(ls[i], q, 0, [*r, i]) 
      or find_element(ls, q, i   1, r)
  elif ls[i] == q:
    return [*r, i]
  else:
    return find_element(ls, q, i   1, r)
  

 print(find_element(input, 5))
# [1, 0]

print(find_element(input, 2000))
# [3, 1, 3, 1, 0]

print(find_element(input, 999))
# None