Как улучшить алгоритм увеличения подзаследований для включения не отсортированного массива?

Question

Я работаю над решением проблемы увеличения подпоследовательности. Алгоритм, который я придумал, в настоящее время решает только для отсортированных массивов. Я пишу свой код в python 3.5. Эта проблема размещена на Leetcode.

При увеличении проблемы подпоследовательности, мне дает целочисленный массив, задача состоит в том, чтобы найти все различные возможные возрастающие подпоследовательности данного массива, а длина возрастающей подпоследовательности должна быть по крайней мере 2.

Пример :

Вход- [4,6,7,7]

Выход - [[4,6], [4,7], [4,6,7], [4,6,7, 7], [6,7], [6,7,7], [7,7], [4,7,7]]

Это мой рабочий код для решения вопроса:

array = [4,6,7,7] 

def incrSubseq(array): #Only works for sorted arrays. 
    res = [[]] 
    ans = [] 
    for num in array: 
     res += [item + [num] for item in res if (item+[num] not in res)] 
    for values in res: 
     if len(values)>1: 
      ans = ans + [values] 
    print(ans) 
incrSubseq(array) 

Как работает этот код?

1. Он начинается с инициализации переменной результат res (список списков) который инициализируется пустым списком.
2. Затем я перебираю заданный массив целых чисел array, который находится в отсортированном порядке, добавляя каждый элемент в список, таким образом, можно найти все подмножества, которые могут быть сформированы. Оператор if внутри распознавания списка отфильтровывает элементы, дублирующие и сохраняя при этом только одну копию списка.
3. Тогда я фильтровать весь массив, который имеет длину больше 1.

Таким образом, решение проблемы.

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

res += [item + [num] for item in res if (item+[num] not in res) and (item <= num)] который дает в пустых списках.

Любые предложения по улучшению кода?

Answer 1

Ваша идея полностью верна! Просто проверьте, был ли последний элемент в item меньшим, чем предыдущий (возможно, разрешить равный, в зависимости от того, как один из них увеличивается).

Итак, вы добавляете чек item[-1] <= num (с -1 вы получаете последний элемент массива в Python).

Теперь есть еще одна проблема. item может быть пустым, и вы получите сообщение об ошибке. Поэтому вы хотите, чтобы этот <= проверял, есть ли хотя бы один элемент в item. Ниже приводится примерное решение с использованием короткого замыкания булевых операций, где (len(item) == 0 or item[-1] <= num) истинно, когда либо нет элемента (тогда выполняется вторая проверка , а не), либо имеется хотя бы один элемент в item, и вы проверяете, меньше ли он или равным.

array = [4,6,3,7] 

def incrSubseq(array): # Works for sorted arrays too :) 
    res = [[]] 

    for num in array: 
     res += [item + [num] for item in res if (item + [num] not in res 
               and (len(item) == 0 or item[-1] <= num))] 

    return [values for values in res if len(values) > 1] 

print(incrSubseq(array)) 

---

Short circuiting означает, что логическое выражение вычисляется только до тех пор, его конечное значение не может быть определена. Например, False and 1/0 не вызвало бы исключение, поскольку and равно False, если любой из из двух своих аргументов: False. Поэтому, когда оценка идет слева направо, он не рассчитает 1/0.

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

for num in array: 
    for item in res: 
     if item + [num] not in res: 
      if len(item) == 0: 
       # item is empty. 
       res += [num] 
      else: 
       # item is not empty so we check its last element. 
       if item[-1] <= num: 
        res += item + [num] 
       else: 
        # We got something increasing here. Do not add. 
        pass 

---

сложность этого алгоритма может быть вычислено, как следует. Предположим, что наихудший случай ввода [1, 2, ..., n]. Затем на каждом шаге число полученных подпоследовательностей удваивается, что приводит к подпоследовательности O(2^n) и выходному размеру O(n * 2^n). Каждый алгоритм займет, по крайней мере, такой длинный (если вы действительно заинтересованы в выводе каждой последовательности - если вы хотите генерировать все на лету aka. Итератор и ленивый стиль оценки функциональных языков это не имеет значения).

Эти алгоритмы занимают гораздо больше времени. Основная работа, которую мы должны выполнить для каждой подпоследовательности на выходе, - проверить, будет ли она дублировать наивное item + [num] not in res. Сравнение двух списков длины m принимает O(m) наихудший случай. И учитывая, что последний num занимает более половины общей продолжительности работы, мы просто используем его в качестве хорошего приближения здесь. Это означает, что проверка последних 2^(n-1) созданных подпоследовательностей принимает O(2^(n-1) * 2^(n-1) * n) = O(n * 4^n), потому что вы проверяете каждую новую последовательность со всеми старыми. С prefix tree, в результате, структура данных может быть уменьшена до O(2^n), так как эта проверка, если действительна новая подпоследовательность, требует только O(1). Перемещение дерева для фактического записи всех решений требует затем снова O(2^n * n).

Sidenote: Если вы любите функциональное программирование в Python проверить syntax_sugar_python,