Find a polynomial time algorithm or prove np-hardness for the following problem: given two strings s1=a1, a2,...,ak and s2=b1,...,bk, where s2 is a random permutation of s1. We now want to build s1 out of s2. A construction works as follows. Pick a letter from s2, that is equal to a1 and remove it. Proceed, with letter a2 and remove it and so on, until s2 is empty. Note, that the same letter can occur multiple times in s2. Let C = c1, c2,...,ck be the constructed sequence, so that C = s1. We define l to be the number of times we need to jump back in s2 to pick the next letter. For example, if we chose c3 and c4, but the index of c4 in the original s2 is smaller than the index of c3 in the original s2, we increment l by one. Our task is, to find the optimum sequence, so that l is minimal. If we are given s1=abac and s2=acab for example, the output has to be 1, since we can pick the second "a" from s2, then choose "b", then jump back and pick the first "a", then add "c".
I don't know how to solve this problem in polynomial time. I thought maybe there is some way to calculate a perfect matching and read of the optimal sequence, but i am not sure. So far, i have only an exponential algorithm.
I tried finding a polynomial algorithm, but i didn't find it
The exponential algorithm looks as follows(not sure if it is correct, don't know how to test it):
def solvenaive(s1, s2, curr_ind):
if len(s1) == 0:
return 0
first_s1 = s1[0]
vorkommen = findOccurrences(s2, first_s1)
results = []
for i in vorkommen:
new_s1 = s1[1:]
new_s2 = stringPop(s2, i)
res = solvenaive(new_s1, new_s2, i)
if curr_ind > i:
results.append(res+1)
else:
results.append(res)
return min(results)
from Construct string from its permutation with least jumps back
No comments:
Post a Comment