Dynami c Программирование для самой короткой подпоследовательности, которая не является подпоследовательностью двух строк

Question

Проблема: При заданных двух последовательностях s1 и s2 из '0' и '1' вернуть самую короткую последовательность, которая является подпоследовательностью ни одной из двух последовательностей.

Например, s1 = '011' s2 = '1101 'Return s_out =' 00 'как один из возможных результатов.

Обратите внимание, что подстрока и подпоследовательность отличаются, когда подстрока символов является смежной, но в подпоследовательности, которая не должна иметь место.

Мой вопрос : Как применяется динамическое c программирование в «Решении, предоставленном» ниже, и какова его временная сложность?

Моя попытка включает в себя вычисление всех подпоследовательностей для каждой строки, дающей sub1 и sub2. Добавьте «1» или «0» к каждому sub1 и определите, нет ли этой новой подпоследовательности в sub2.Найдите минимальную длину. Вот мой код:

Мое решение

def get_subsequences(seq, index, subs, result): 
    if index == len(seq): 
        if subs: 
            result.add(''.join(subs))
    else:
        get_subsequences(seq, index + 1, subs, result)
        get_subsequences(seq, index + 1, subs + [seq[index]], result)

def get_bad_subseq(subseq):
    min_sub = ''
    length = float('inf')
    for sub in subseq:
        for char in ['0', '1']:
            if len(sub) + 1 < length and sub + char not in subseq:
                length = len(sub) + 1
                min_sub = sub + char
    return min_sub

Предоставленное решение (не мое)

Как это работает и сложность его времени?

Это выглядит, что приведенное ниже решение выглядит так: http://kyopro.hateblo.jp/entry/2018/12/11/100507

def set_nxt(s, nxt):
    n = len(s)
    idx_0 = n + 1
    idx_1 = n + 1
    for i in range(n, 0, -1):
        nxt[i][0] = idx_0
        nxt[i][1] = idx_1
        if s[i-1] == '0':
            idx_0 = i
        else:
            idx_1 = i
    nxt[0][0] = idx_0
    nxt[0][1] = idx_1

def get_shortest(seq1, seq2):
    len_seq1 = len(seq1)
    len_seq2 = len(seq2)
    nxt_seq1 = [[len_seq1 + 1 for _ in range(2)] for _ in range(len_seq1 + 2)] 
    nxt_seq2 = [[len_seq2 + 1 for _ in range(2)] for _ in range(len_seq2 + 2)] 

    set_nxt(seq1, nxt_seq1)
    set_nxt(seq2, nxt_seq2)

    INF = 2 * max(len_seq1, len_seq2)
    dp = [[INF for _ in range(len_seq2 + 2)] for _ in range(len_seq1 + 2)]
    dp[len_seq1 + 1][len_seq2 + 1] = 0
    for i in range( len_seq1 + 1, -1, -1):
        for j in range(len_seq2 + 1, -1, -1):
            for k in range(2):
                if dp[nxt_seq1[i][k]][nxt_seq2[j][k]] < INF:
                    dp[i][j] = min(dp[i][j], dp[nxt_seq1[i][k]][nxt_seq2[j][k]] + 1);

    res = ""
    i = 0
    j = 0
    while i <= len_seq1 or j <= len_seq2:
        for k in range(2):
            if (dp[i][j] == dp[nxt_seq1[i][k]][nxt_seq2[j][k]] + 1):
                i = nxt_seq1[i][k]
                j = nxt_seq2[j][k]
                res += str(k)
                break;
    return res

Answer 1

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

Простое построение этого массива занимает пространство (и, следовательно, время) O(len(seq1) * len(seq2)). На его заполнение уходит примерно столько же времени.

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

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

ОБНОВЛЕНИЕ :

Здесь все закодировано. С плохим выбором имен переменных. Извините за это.

# A trivial data class to hold a linked list for the candidate subsequences
# along with information about they match in the two sequences.
import collections
SubSeqLinkedList = collections.namedtuple('SubSeqLinkedList', 'value pos1 pos2 tail')

# This finds the position after the first match.  No match is treated as off the end of seq.
def find_position_after_first_match (seq, start, value):
    while start < len(seq) and seq[start] != value:
        start += 1
    return start+1

def make_longer_subsequence (subseq, value, seq1, seq2):
    pos1 = find_position_after_first_match(seq1, subseq.pos1, value)
    pos2 = find_position_after_first_match(seq2, subseq.pos2, value)
    gotcha = SubSeqLinkedList(value=value, pos1=pos1, pos2=pos2, tail=subseq)
    return gotcha

def minimal_nonsubseq (seq1, seq2):
    # We start with one candidate for how to start the subsequence
    # Namely an empty subsequence.  Length 0, matches before the first character.
    candidates = [SubSeqLinkedList(value=None, pos1=0, pos2=0, tail=None)]

    # Now we try to replace candidates with longer maximal ones - nothing of
    # the same length is better at going farther in both sequences.
    # We keep this list ordered by descending how far it goes in sequence1.
    while candidates[0].pos1 <= len(seq1) or candidates[0].pos2 <= len(seq2):
        new_candidates = []
        for candidate in candidates:
            candidate1 = make_longer_subsequence(candidate, '0', seq1, seq2)
            candidate2 = make_longer_subsequence(candidate, '1', seq1, seq2)
            if candidate1.pos1 < candidate2.pos1:
                # swap them.
                candidate1, candidate2 = candidate2, candidate1
            if candidate1.pos1 < candidate2.pos1:
                # swap them.
                candidate1, candidate2 = candidate2, candidate1
            for c in (candidate1, candidate2):
                if 0 == len(new_candidates):
                    new_candidates.append(c)
                elif new_candidates[-1].pos1 <= c.pos1 and new_candidates[-1].pos2 <= c.pos2:
                    # We have found strictly better.
                    new_candidates[-1] = c
                elif new_candidates[-1].pos2 < c.pos2:
                    # Note, by construction we cannot be shorter in pos1.
                    new_candidates.append(c)
        # And now we throw away the ones we don't want.
        # Those that are on their way to a solution will be captured in the linked list.
        candidates = new_candidates

    answer = candidates[0]
    r_seq = [] # This winds up reversed.
    while answer.value is not None:
        r_seq.append(answer.value)
        answer = answer.tail

    return ''.join(reversed(r_seq))


print(minimal_nonsubseq('011', '1101'))