Сортировка узлов дерева по ширине в порядке нумерации

Question

Предположим, у меня есть следующий массив numpy:

arr = numpy.array([[1, 7], [2, 0], [2, 1], [2, 3], [3, 4], [3, 5], [5, 6]])

Предположим, я выбрал определенный ключ, в данном случае 2.Тогда я бы хотел, чтобы сортировка была следующей:

arr_sorted = [[2, 0], [2, 1], [2, 3], [1, 7], [3, 4], [3, 5], [5, 6]]

Идея состоит в том, чтобы сначала начать со всех элементов с ключом, равным 2, а затем перейти к записям, ключи которых были значениями предыдущего ключа.

Начиная с 2, записи [2, 0], [2, 1], [2, 3].Следовательно, следующие ключи после 2 будут 0, 1, 3. Нет записей с 0 в качестве ключа.Существует одна запись с ключом 1: [1, 7].Есть две записи с ключом 3: [3, 4], [3, 5].Следующий необработанный ключ - 7, но в нем нет записей.То же самое для 4. Есть одна запись с 5 в качестве ключа: [5, 6].6 не имеет записей.

Есть ли какие-нибудь хитрости numpy или dictionary для достижения этой цели?

Моя ближайшая попытка следующая:

def bfs_finder(d, start):
  queue = deque([start])
  seen = [start]
  results = []
  while queue:
    _vertices = queue.popleft()
    current = [i for i, a in enumerate(d) if len([x for x in a if x in _vertices])==1 and i not in seen]
    curr1 = [a[1] for i, a in enumerate(d) if len([x for x in a if x in _vertices]) == 1 and i not in seen]
    if len(current)>0:
        results.extend(curr1)
        queue.extend(curr1)
        seen.extend(current)
  return results

Но,Я на самом деле получаю ошибку current = [i for i, a in enumerate(d) if len([x for x in a if x in _vertices])==1 and i not in seen] TypeError: argument of type 'int' is not iterable.Будем весьма благодарны за любые предложения о том, как исправить эту ошибку, а также о каких-либо хороших улучшениях.

Answer 1

Вы можете использовать set для хранения обработанных ключей и deque или подобный совместимый со стеком контейнер для хранения обработанных значений (список также будет работать),Поскольку у вас есть пустые массивы, вы можете предварительно отсортировать массив по строкам и извлечь из него ряды, используя np.searchsorted в первом столбце.

Алгоритм будет выглядеть примерно так:

1. Сортировка массива по строкам
2. Предварительное выделение выходного массива
3. Добавление ключа в stack
4. Пока стек не пуст
5. Вытащить ключ из стека
6. Если ключ находится в наборе, сбросить и продолжить
7. Добавить ключ к набору
8. Найти ключ в первом столбце (начало иконечные индексы) с использованием деления пополам
9. Если ключ присутствует, скопируйте полосу в выходной массив

Операция сортировки O(n log(n)).Также будет использоваться алгоритм деления пополам (примерно n поисков с O(log(n)) каждый).Таким образом, ваша общая алгоритмическая сложность не должна превышать O(n log(n)), что довольно неплохо для странного алгоритма сортировки.

Сортировка по строкам кажется наиболее быстрой с использованием np.argsort в соответствии с этот ответ , и, к счастью, np.searchsorted принимает аргумент sorter.

Вот пример реализации:

import numpy as np
from collections import deque

def bfs_finder(d, start):
    sorter = np.argsort(d[:, 0])
    done = set()
    todo = deque([start])
    output = np.empty_like(d)
    pos = 0
    while todo:
        key = todo.popleft()
        if key in done:
            continue
        done.add(key)
        left = np.searchsorted(d[:, 0], key, 'left', sorter)
        if left >= d.shape[0] or d[sorter[left], 0] != key:
            continue
        right = np.searchsorted(d[:, 0], key, 'right', sorter)
        next = pos + right - left
        output[pos:next, :] = d[sorter[left:right], :]
        todo.extend(output[pos:next, 1])
        pos = next
    return output

arr = np.array([[1, 7], [2, 0], [2, 1], [2, 3], [3, 4], [3, 5], [5, 6]])
print(bfs_finder(arr, 2))

IDEOne Link

[[2 0]
 [2 1]
 [2 3]
 [1 7]
 [3 4]
 [3 5]
 [5 6]]

В этом решении предполагается, что в оригинале не будет ключей, отсутствующих в выходных данных.Если вы столкнулись с этой проблемой, вычтите набор первого столбца из набора обработанных ключей и решите, как вы хотите обработать остаток.

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