Python - Как отсортировать многомерный список в двумерный список?

Question

Как я могу отсортировать многомерный список в двумерный список?

Многомерный ввод: [8, [6, 7, [-1], [4, [[10]]], 2], 1]

Требуемый двумерный вывод: [[8, 1], [6, 7, 2], [-1, 4], [], [10]]

все то же самоеэлементы списка глубины должны быть в одном списке.

Answer 1

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

def extract_entries(nested_list, new_list=[]):
    # Add the list of all of the items in <nested_list> that are NOT lists themselves. 
    new_list.append( [ e for e in nested_list if type(e) != list ] )

    # Look at entries in <nested_list> that ARE lists themselves.
    for entry in nested_list:
        if type(entry) == list:
            extract_entries(entry, new_list)

    return new_list

Тестирование:

M = [8, [6, 7, [-1], [4, [[10]]], 2], 1]
print(extract_entries(M))
# Returns: [[8, 1], [6, 7, 2], [-1], [4], [], [10]]

Answer 2

Мой вариант с рекурсией и без каких-либо зависимостей:

lst = [8, [6, 7, [-1], [4, [[10]]], 2], 1]

def flat_group(lst, deep = 0, res = None):
  if res == None: res = []
  for item in lst:
    if len(res) <= deep: res.append([])
    if not type(item) == list:
      res[deep].append((item))
    else:
      flat_group(item, deep + 1, res)
  return res


print(flat_group(lst))
#=> [[8, 1], [6, 7, 2], [-1, 4], [], [10]]

---

Чтобы показать Как это работает , я разделил метод на две части:

def flat(lst, deep = 0, res = []):
  for item in lst:
    if not type(item) == list:
      res.append((deep, item))
    else:
      flat(item, deep + 1, res)
  return res

def group(lst):
  flatten = flat(lst)
  max_n = max(flatten)[0]
  res = [[] for _ in range(0,max_n+1)]
  for deep, item in flatten:
    res[deep].append(item)
  return res

print(group(lst))
#=> [[8, 1], [6, 7, 2], [-1, 4], [], [10]]

flat(lst) - это рекурсивный метод, который создает плоский список кортежей, где каждый кортеж содержит значение и глубину внутри исходного списка.Таким образом, вызов flat(lst) возвращает:

# [(0, 8), (1, 6), (1, 7), (2, -1), (2, 4), (4, 10), (1, 2), (0, 1)]

Затем group(lst) создает список из n+1 пустого подсписка, где n - максимальная глубина, он повторяется по результату flat(lst) и добавьте каждый элемент по индексу в соответствующий подсписок.

flat_group(lst) делает почти то же самое.

Answer 3

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

from collections import deque
def flatten(lst):
    output = []
    q = deque([(lst, 0)])
    while q:
        l, depth = q.popleft()
        for i in l:
            if isinstance(i, list):
                q.append((i, depth + 1))
            else:
                while depth >= len(output):
                    output.append([])
                output[-1].append(i)
    return output

, так что:

flatten([8, [6, 7, [-1], [4, [[10]]], 2], 1])

возвращает:

[[8, 1], [6, 7, 2], [-1, 4], [], [10]]

Answer 4

Идея в основном та же, что и в ответе @TerryA, но с использованием setdefault и проверкой в ​​конце цикла for, было ли добавлено что-то из глубины:

lst = [8, [6, 7, [-1], [4, [[10]]], 2], 1]


def depths(l):
    def flatten(l, start=0, depth={}):

        for e in l:
            if isinstance(e, list):
                flatten(e, start=start + 1, depth=depth)
            else:
                depth.setdefault(start, []).append(e)
         if start not in depth:
            depth[start] = []

    d = {}
    flatten(l, depth=d)

    return [d[i] for i in range(max(d) + 1)]


result = depths(lst)
print(result)

Выход

[[8, 1], [6, 7, 2], [-1, 4], [], [10]]

Answer 5

Вы можете сделать это, сначала создав словарь элементов на каждой глубине (с глубиной в качестве ключа в этом словаре и списком элементов этой глубины в качестве значения).Рекурсивная функция get_elements_by_depth ниже делает это.Тогда все, что вам нужно сделать, это сгладить значения этого словаря.(функция flatten_by_depth ниже делает то, что вам нужно).

from collections import defaultdict

def get_elements_by_depth(ls, cur_depth, cur_dict):
    """
        returns a dictionary with depth as key and a list of all
        elements that have that depth as value
    """
    for x in ls:
        if isinstance(x, list):
            get_elements_by_depth(x, cur_depth + 1, cur_dict)
        else:
            cur_dict[cur_depth].append(x)
    return cur_dict


def flatten_by_depth(ls):
    """
        returns a list of lists, where the list at index i 
        contains all elements of depth i
    """
    elements_by_depth = get_elements_by_depth(ls, 0, defaultdict(list))
    max_depth = max(elements_by_depth.keys())
    # Since we're using a defaultdict, we don't have to worry about
    # missing keys in elements_by_depth
    return [
        elements_by_depth[i]
        for i in xrange(max_depth + 1)
    ]

---

> flatten_by_depth([8, [6, 7, [-1], [4, [[10]]], 2], 1])
[[8, 1], [6, 7, 2], [-1, 4], [], [10]]

Answer 6

Возможно, вы могли бы использовать defaultdict здесь для измерения глубины каждого элемента вместе с рекурсией:

from collections import defaultdict
L = [8, [6, 7, [-1], [4, [[10]]], 2], 1]
res = defaultdict(list)
def myfunc(L, depth):
    for i in L:
        if isinstance(i, list):
            myfunc(i, depth+1)
        else:
            res[depth].append(i)

myfunc(L, 0)

Тогда defaultdict будет выглядеть так:

defaultdict(<class 'list'>, {0: [8, 1], 1: [6, 7, 2], 2: [-1, 4], 4: [10]})

Затем вам нужно будет перевести defaultdict обратно в то, что вы хотите.Обратите внимание, что по умолчанию dict не будет содержать пустой список, потому что он не может его обнаружить (то есть: [[10]] и [10] оба списка), но то, что он будет иметь, - это пробел в диапазоне (обратите внимание, как глубина 3 отсутствует в defaultdict).

final = []
for i in range(max(res)+1):
    if i not in res:
        final.append([])
    else:
        final.append(res[i])

print(final)

Очень грязно, я уверен, что улучшения могут быть сделаны.