CODEWITHSUNDEEP
pythonalgorithm
Simd
Simd

Reputation: 21353

How to print the subsequence found using dynamic programming

I have written code to compute the longest palindrome subsequence.

def longest_pal_subseq(sequence, i, j):
    if (i == j): 
        return 1
    if (sequence[i] == sequence[j] and j - i == 1): 
        return 2
    if (sequence[i] == sequence[j]): 
        return longest_pal_subseq(sequence, i + 1, j - 1) + 2
    return max(longest_pal_subseq(sequence, i, j - 1),  
               longest_pal_subseq(sequence, i + 1, j)) 

if __name__ == '__main__': 
    sequence = "abracadabra"
    print("Length: ", longest_pal_subseq(sequence, 0, len(sequence)  - 1))

But how can the code be modified to also print the subsequence it has found of that length?

Upvotes: 0

Views: 154

Answers (2)

Tls Chris
Tls Chris

Reputation: 3934

Edit: The original answer had a bug.
This is fastest and easiest to follow but doesn't use dynamic programming. It only returns contiguous palindromes not as required by the question.

def is_pal(string):
    return string == string[:: -1]

def longest_pal(string):
    full = len(string)
    for length in range(full, -1, -1):
        for i in range(full-length+1):
            if is_pal(string[i:length+i]):
                return length, i, string[i:length+i]

longest_pal('abracadabra')
# (3, 3, 'aca')

I can see 2 palindromes of length 3 'aca' and 'ada' but none of length 7.

A second approach uses a dictionary res_so_far to store the sequences with their longest palindromic subsequence. If the same sequence is processed more than once the result is returned from the dictionary without running the rest of the recursive function calls. This returns non contiguous palindromic sequences in the base sequence.

def longest(a, b):
        if len(a) >= len(b): return a
        return b


def longest_pal_in( sequence ):

    res_so_far = {}  # To store intermediate results as they are found.
    def set(seq, res):
        """ set result so far then return result. 
            This is incorporated in each return statement in longest_pal 
        """
        res_so_far[seq] = res
        return res

    def longest_pal( sequence ):
        try:
            return res_so_far[sequence]
            # If sequence is stored in res_so_far return the result
        except KeyError: # If not run the rest of the function
            pass

        if len( sequence ) < 4:
            if sequence[0] == sequence[-1]:  # len 1,2, or 3 if first == last then palindrome
                return set(sequence, sequence)
        elif sequence[0] == sequence[-1]:
            # Changed to find sub sequences, not substrings        
            return set(sequence, sequence[0]+longest_pal( sequence[1:-1] )+sequence[-1] )
            # Three lines below removed to return non contiguous sub sequences.
            # sub = longest_pal( sequence[1:-1] )
            # if len(sub) == (len(sequence) - 2):
            #     return set(sequence, sequence)
        return set(sequence, longest(longest_pal( sequence[:-1] ), longest_pal( sequence[1:] )))

    return longest_pal(sequence)

Timings

test = 'abracadabra'

%timeit longest_pal(test)  # Not recursive
# 54.4 µs ± 765 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit longest_pal_in(test)  # Recursive
# 93.5 µs ± 2.95 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit longest_pal_in(test+test)
# 369 µs ± 5.62 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit longest_pal_in(test+test+test)
# 784 µs ± 39.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

longest_pal_in performs roughly O(n^2)

HTH

Upvotes: 1

hookedonwinter
hookedonwinter

Reputation: 12666

You could return a dictionary with the palindrome and length.

return {"length": max(longest_pal_subseq(sequence, i, j - 1),  
           longest_pal_subseq(sequence, i + 1, j)),
        "palindrome": sequence}

You'd have to alter the longest_pal_subseq to use the dict throughout as well.

Upvotes: 0

Related Questions