Рекурсивное самостоятельное соединение и транспонирование

Question

У меня есть набор данных, который отслеживает родительские / дочерние отношения в течение нескольких циклов измерения. Это выглядит как

[["Col1","Col2"],
 ["A","B"],
 ["B","C"],
 ["C","D"]]

Я бы хотел, чтобы это выглядело как

[["Col1","Col2","Col3","Col4"],
 ["A","B","C","D"]]

Я видел другие примеры в SQL, но ни один из них, похоже, не отвечает на мой вопрос. Я ищу полное столбчатое расширение данных.

Я исследовал самосоединения и транспонирования, но ни один из них не привел меня туда.

Это не требует гиперспециализированных пакетов Python, так как мне нужно перенести это на несколько других языков программирования.

Обновление: второй пример: Если бы у меня был набор данных, такой как

[["Col1","Col2"],
 ["A","B1"],
 ["B1","C1"],
 ["B1,"C2"],
 ["C2,"D"],
 ["A,"B2"]]

Я бы ожидал:

[["Col1","Col2","Col3","Col4"],
 ["A","B1","C1",""],
 ["A","B1","C2","D"],
 ["A","B2","",""]]

Answer 1

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

def join(pairs):
    def _join(parent=None):
        if parent not in tree:
            return [[parent]]
        output = []
        for child in tree[parent]:
            for joined in _join(child):
                output.append([*([parent] if parent else []), *joined])
        return output
    tree = {}
    children = set()
    for parent, child in pairs:
        tree.setdefault(parent, []).append(child)
        children.add(child)
    for parent in tree.keys() - children:
        tree.setdefault(None, []).append(parent)
    return _join()

так что дано:

pairs = [
    ["A", "B1"],
    ["B1", "C1"],
    ["B1", "C2"],
    ["C2", "D"],
    ["A", "B2"]
]

joined(pairs) вернется:

[['A', 'B1', 'C1'], ['A', 'B1', 'C2', 'D'], ['A', 'B2']]

Теперь, если вы хотите заполнить строки меньшим количеством столбцов пустыми строками, вы можете сначала получить максимальное количество столбцов, а затем выполнить итерацию по строкам, чтобы расширить их достаточным количеством пустых строк, чтобы сделать их равным числу столбцов:

joined = join(pairs)
max_columns = max(map(len, joined))
for path in joined:
    path.extend([''] * (max_columns - len(path)))

joined станет:

[['A', 'B1', 'C1', ''], ['A', 'B1', 'C2', 'D'], ['A', 'B2', '', '']]

Обратите внимание, что я игнорирую заголовки столбцов, такие как ['Col1', 'Col2'], в вашем вопросе, поскольку они не имеют отношения к проблеме, и вы не предоставили объяснения, откуда взялись 'Col3' и 'Col4'.

Answer 2

дает желаемый результат:

fam = [["Col1","Col2"],["A","B"],["B","C"],["C","D"]]

col, chi, res = [], [], []

for i in fam:
    for ii in i:
        if len(ii) == 1:
            if ii in chi:
                chi.remove(ii)
            chi.append(ii)
        else:
            col.append(ii)

res.append(col)
res.append(chi)

>>>print(res)
>>>[['Col1', 'Col2'], ['A', 'B', 'C', 'D']]