Блог

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

 a_list = [1, 2, 3, 4, 8, 7, 6]
  

Мы хотим найти наименьшее ‘число’ возрастающих последовательностей, содержащих все элементы списка с обеих сторон списка.

Для приведенного выше примера мы получим

последовательность = [[1,2,3,4,8], [6,7]]

Что дает ответ 2. Это потому, что мы можем сформировать возрастающую последовательность слева направо как [1,2,3,4,8] . Мы также можем сформировать возрастающую последовательность справа налево как [6,7] .

Я рассмотрел возможность создания двух списков, которые дают все возрастающие последовательности списка и обратные списку, как таковые

 left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]
  

но я не уверен, куда идти дальше. Есть мысли?

РЕДАКТИРОВАТЬ: приведенный ниже оригинал излишне сложен. Увеличение «слева» просто означает уменьшение. Поэтому просто выполните итерацию по списку один раз, отслеживая возрастающие и убывающие последовательности с помощью логического флага, делая их как можно длиннее, а затем посчитайте в конце. Это должно сработать. Не проверено.

 increasing = None
current_item = _list[0]
all_sequences = []
current_sequence = [_list[0]]

for item in _list[1:]:
    if increasing is None:
        increasing = item > current_sequence[-1]
        current_sequence.append(item)

    elif (item > current_item and increasing) or (item < current_item and not increasing):
        current_sequence.append(item)

    elif (item > current_item and not increasing) or (item < current_item and increasing):
        all_sequences.append(current_sequence)
        current_sequence = [item]
        increasing = None
    
    current_item = item
all_sequences.append(current_sequence)
result = len(all_sequences)
        



    
  

Оригинальный ответ:
Вот несколько мыслей

Во-первых, я предполагаю, что ваша функция всегда будет делать последовательности как можно длиннее. Итак, вы получаете это:

 left_to_right = [[1,2,3,4,8],[7], [6]]
  

А не, например, это:

 left_to_right = [[1,2],[3],[4,8],[7], [6]]
  

(который технически также является списком возрастающих последовательностей).

Ваша следующая задача — убедиться, что вы получили все числа в списке. Итак, вы должны выбрать несколько возрастающих последовательностей. Чем длиннее выбранная вами последовательность, тем больше чисел вы получаете для «использования», не добавляя слишком много последовательностей. Чтобы взять ваш пример:

 left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]
  

Соедините два списка вместе:

 all = left_to_right   right_to_left
  

Теперь найдите самую длинную последовательность:

 longest = max(all, key=lambda x:len(x))
  

Это даст вам

 [1,2,3,4,8]
  

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

 [[1,2,3,4,8], [6,7,8]]
  

В качестве последнего шага проверьте наличие дубликатов. Тогда вы получите

 [[1,2,3,4,8], [6,7]]
  

по желанию

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