Сбор подпоследовательностей из последовательности

Question

Допустим, у нас есть следующая последовательность:

[1, 2, 1, 1]

Мы хотим вычислить все подпоследовательности из данной последовательности в соответствии со следующим правилом:

if s_i <= s_i+1 then s_i+1 is part of a subsequence with s_i

Подпоследовательность вычисляетсяначиная с первого элемента последовательности, здесь 1, и сравнивая его с его правым соседом, здесь 2.Если они применяются к условию, то образуют подпоследовательность.После этого 2 необходимо сравнить с его правым соседом 1, и, если они применяются, он присоединяется к подпоследовательности.Здесь они этого не делают, поэтому он не присоединяется.

Этот процесс продолжается с 2 и соседом предыдущего соседа 1 до конца последовательности.После этого процесс продолжается с соседом 2 аналогичным образом.

На следующем графике показан процесс построения подпоследовательности для первого элемента 1 в последовательности:

Следовательно, проблема носит рекурсивный характер.Вот код:

def calc(seq):
    for i in range(0, len(seq)):
          calc_subseq(i, seq)

def calc_subseq(i, seq):
       a = seq[i]
       for j in range(i+1, len(seq):
           b[j] = seq[j]
           if b <= a:
               calc_subseq(j, seq);
           else:
                #build subsequence
        #build subsequnce

Вопрос теперь:

Как получить подпоследовательности после их вычисления?Я использовал стек и передавал его при каждом вызове.Кроме того, я передал счетчик, который увеличивается с каждым совпадением и передается при каждом вызове функции, а также возвращается впоследствии.В случае несоответствия я выбрасываю из стека столько предметов, сколько считает счетчик.Я делаю то же самое, когда конец цикла for достигается в calc_subseq(seq).Но я ищу лучшее решение.

Кто-нибудь знает какой-либо алгоритм для решения подобных проблем?Было бы довольно интересно, если бы был более эффективный способ.Я думал о каком-то динамическом программировании.

Редактировать:

В соответствии с запросом, здесь приведены все результаты для входной последовательности [1,2,1,1]:

1 (0), 2 (1)
2 (1)
2 (1)
2 (1) -> end
1 (0), 1 (2), 1 (3) 
1 (3) -> end
1 (2) -> end 
1 (0), 1(3)
1 (3) -> end
1 (0) -> end
2 (1)
2 (1)
2 (1) -> end
1 (2), 1 (3)
1 (3) -> end
1 (2) -> end
1 (3) -> end

Примечание: Индексы представлены как (x).-> end указывает, что был достигнут конец второго цикла for.Следовательно, он показывает последний элемент, который нельзя сравнить, потому что не осталось соседа.

Answer 1

Существует серьезная проблема.Если исходная последовательность имеет длину n, самая длинная восходящая подпоследовательность имеет ожидаемую длину O(sqrt(n)), и каждое подмножество этой последовательности является другой восходящей подпоследовательностью, поэтому их не менее O(exp(sqrt(n))).Если n имеет даже умеренный размер, число таких подпоследовательностей быстро становится очень, очень большим.

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

def rising_tree (seq):
    tree = {}
    for item in reversed(seq):
        this_count = 1 # For the subsequence of just this item
        this_next = {}
        for next_item, data in tree.items():
            if item <= next_item:
                this_count = this_count + data[0]
                this_next[next_item] = data
        tree[item] = [this_count, this_next]
    total_count = 0
    for _, data in tree.items():
        total_count = total_count + data[0]
    return [total_count, tree]

При применении к вашему примеру [1, 2, 1, 1] вы получите следующую структуру данных:

[   5, # How many rising subsequences were found
    {   1: [   4, # How many start with 1
               {   1: [   2,  # How many start with 1, 1
                          {   1: [   1, # How many start with 1, 1, 1
                                     {   }]}],
                   2: [   1, # How many start with 1, 2
                          {   }]}],
        2: [   1, # How many start with 2
           {   }]}]

И теперь мы можем извлечь их все следующим образом:

def tree_sequence_iter (tree):
    items = sorted(tree[1].keys())
    for item in items:
        yield [item]
        subtree = tree[1][item]
        if (subtree[1]):
            for subseq in tree_sequence_iter(subtree):
                yield [item] + subseq


for ss in tree_sequence_iter(rising_tree([1, 2, 1, 1])):
    print(ss)

Обратите внимание, что мне не нужен звонок на sorted, который я там проскользнул, но с этим мы невыводим только уникальные подпоследовательности, мы получаем их в лексикографическом порядке!(Хотя имейте в виду, что их может быть много.)

И если вы действительно не хотите генератора (и думаете, что у нас есть память для его хранения), мы можем просто list(tree_sequence_iter(rising_tree(seq)))создать наш список.