Удаление лишних значений ссылающихся друг на друга объектов

Question

У меня есть примерно такой список (упрощено до общей реализации)

a = [
['0', 11], 
['1', 3], 
None, 
['3', None], 
['4', 6], 
['5', None],
['6', None], 
['7', 10], 
None, 
['9', 4], 
['10', 11], 
['11', None]
]

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

print(a[a[0][1]])  # Выведет ['11', None]
print(a[a[1][1]])  # Выведет ['3', None]
print(a[a[4][1]])  # Выведет ['6', None]
print(a[a[7][1]])  # Выведет ['10', 11]
print(a[a[9][1]])  # Выведет ['4', 6]
print(a[a[10][1]]) # Выведет ['11', None]

Задача состоит в том, чтобы удалить из данного списка все None элементы так, чтобы эти ссылки на индексы не съехали. и ссылались на те же самые элементы. То есть чтобы получилось так:

a = [
['0', 9], 
['1', 2], 
['3', None], 
['4', 5], 
['5', None],
['6', None], 
['7', 8], 
['9', 3], 
['10', 9], 
['11', None]
]

При этом значения поменялись, но если получить объект с конкретными данными (1й элемент каждого списка) ссылается на те же самые элементы, что и раньше, хоть и по другим индесам (обратите внимание, что первый элемент, который с данными выводится в том же порядке, что и выше):

print(a[a[0][1]])  # Выведет ['11', None]
print(a[a[1][1]])  # Выведет ['3', None]
print(a[a[3][1]])  # Выведет ['6', None]
print(a[a[6][1]])  # Выведет ['10', 9]
print(a[a[7][1]])  # Выведет ['4', 5]
print(a[a[8][1]]) # Выведет ['11', None]

Индексы поменялись, но сами данные, как можно заметить, не изменились. Я знаю язык и т.д, но не могу разработать сам алгоритм, я пробовал проходить последовательно по массиву, пробовал в обратном порядке, но у меня индексы съезжают. Подскажите пожалуйста, как получить результат, который я ожидаю?

Answer 1

Возможно есть более хитрые алгоритмы, но по тупому делается примерно так - вы проходите по массиву, удаляете ненужные элементы и запоминаете в словаре соответствие старого индекса и нового, новый индекс равен старому минус дельта, дельта перед циклом = 0, при каждом удалении увеличивается на 1. После первого цикла делаете второй цикл по массиву и заменяете индексы в ссылках по словарю:

Вот пример:

def print_array(arr, text):
    print(text)
    for idx, item in enumerate(arr):
        if item and item[1]:
            print(idx, ':', item, '-->', arr[item[1]])
        else:
            print(idx, ':', item)


def delete_none(arr: list):
    old_new = dict()
    delta = 0
# Обратите внимание - первый цикл мы делаем по копии исходного списка
# это необходимо, поскольку мы удаляем элементы прямо в цикле.
# Если мы будем делать цикл по исходному списку, то элемент сразу за удаленным будет потерян для логики.
# Возможно, в python это как-то можно сделать по другому, но я не настолько его знаю
    for idx, item in enumerate(arr[:]):
        if not item:
            del arr[idx - delta]
            delta += 1
        else:
            old_new[idx] = idx - delta

    for item in arr:
        old_index = item[1]
        if old_index:
            if old_index in old_new:
                new_index = old_new[old_index]
                item[1] = new_index
            else:
                item[1] = None


def main():
    a = [
        ['0', 11],
        ['1', 3],
        None,
        ['3', None],
        ['4', 6],
        ['5', None],
        ['6', None],
        ['7', 10],
        None,
        ['9', 4],
        ['10', 11],
        ['11', None]
    ]
    print_array(a, 'Before')
    delete_none(a)
    print_array(a, 'After')


if __name__ == '__main__':
    main()

БЛОГ НА HUSL

Удаление лишних значений ссылающихся друг на друга объектов

Ответы (1 шт):