Определить самый ценный вариант вложенного списка

Question

Есть следующий вложенный список, например:

arr=[[2, 3, 4], [4, 5, 6], [1, 2], [7,8]]

Нужно в нем оставить по уникальному числу таким образом, чтобы остались как можно более длинные вложенные списки. Например, в этом варианте будет два равнозначных варианта, с наибольшим количеством оставшихся символов в наиболее длинных вложенных списках:

arr1=[[4, 5, 6], [2, 3], [7, 8], [1]]

arr2=[[2, 3, 4], [5, 6], [7, 8], [1]]

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

Answer 1

Алгоритм: т.к. мы не можем добавлять и перемещать значения то более длинного подсписка чем есть сейчас мы не получим. Значит осталось сохранить самый длинный подсписок неизмененным. Для этого из всех других подсписком мы удалим те элементы которые есть в нашем выбранном самом длинном подсписке. Потом просто удаляем оставшиеся

Реализация(советую самому это реализовать, но все же):

def maximize(arr):
    # находим саммый длинный подсписок и запоминаем его индекс
    best_ind = -1
    best_value = 0
    for ind in range(len(arr)):
        if len(arr[ind]) > best_value:
            best_value = len(arr[ind])
            best_ind = ind

    # преобразуем его в множество для большей скорости при проверках содержимого
    best_subarray_numbers = set(arr[best_ind]) 

    # у каждого подсписка, кроме нашего удаляем повторы
    for ind in range(len(arr)):
        if ind == best_ind:
            continue
        new_subarray = []
        for value in arr[ind]:
            if not value in best_subarray_numbers:
                new_subarray.append(value)
        arr[ind] = new_subarray

def solve(arr):
    maximize(arr)

    for ind in range(1, len(arr)): # просто удаляем оставшиеся повторы
        subarray_numbers = set(arr[ind]) 
        for ind2 in range(ind+1, len(arr)):
            new_subarray = []
            for value in arr[ind2]:
                if not value in subarray_numbers:
                    new_subarray.append(value)
            arr[ind2] = new_subarray

Примеры:

arr = [[2, 3, 4], [4, 5, 6], [1, 2], [7,8]]
solve(arr)
print(arr) # [[2, 3, 4], [5, 6], [1], [7, 8]]
arr = [[10, 11, 12, 13], [1, 2, 3], [2, 3, 4], [3, 4, 5], [7,8]]
solve(arr)
print(arr) # [[10, 11, 12, 13], [1, 2, 3], [4], [5], [7, 8]]
arr = [[4, 5], [4, 5, 6, 7], [7, 8, 9], [3, 4]]
solve(arr)
print(arr) # [[], [4, 5, 6, 7], [8, 9], [3]]

БЛОГ НА HUSL

Определить самый ценный вариант вложенного списка

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