Answer:
please mark me brainlist
Explanation:
This algorithm works for n number of strings in python3
Input:
83217
8213897
683147
Output:
837
from itertools import product
import pdb
import numpy as np
def neigh(index):
N = len(index)
for ri in product((0, -1), repeat=N):
if not all(i == 0 for i in ri):
yield tuple(i + i_rel for i, i_rel in zip(index, ri))
def longestCommonSubSequenceOfN(sqs):
numberOfSequences = len(sqs); # to know number of sequences
lengths = np.array([len(sequence) for sequence in sqs]); # to know length of each sequences placed in # array
incrLengths = lengths + 1; # here we are taking no .of sequences +1
lengths = tuple(lengths); # making lengths into tuple to make it mutable
inverseDistances = np.zeros(incrLengths);
ranges = [tuple(range(1, length+1)) for length in lengths[::-1]]; # finding ranges from 1 to each lengths
for tupleIndex in product(*ranges):
tupleIndex = tupleIndex[::-1];
neighborIndexes = list(neigh(tupleIndex)); # finding neighbours for each tupled index value and # store them in list
operationsWithMisMatch = np.array([]); # creating array which are miss matched
for neighborIndex in neighborIndexes:
operationsWithMisMatch = np.append(operationsWithMisMatch, inverseDistances[neighborIndex]);
#appending newly created array with operations miss match and inverseDistances
operationsWithMatch = np.copy(operationsWithMisMatch);
# copying newly generated missmatch indexs
operationsWithMatch[-1] = operationsWithMatch[-1] + 1;
# incrementing last indexed value
chars = [sqs[i][neighborIndexes[-1][i]] for i in range(numberOfSequences)];
# finding a string(chars) with neighbour indexes and checking with other sequences
if(all(elem == chars[0] for elem in chars)):
inverseDistances[tupleIndex] = max(operationsWithMatch);
else:
inverseDistances[tupleIndex] = max(operationsWithMisMatch);
subString = ""; # resulted string
mainTupleIndex = lengths; # copying lengths list to mainTupleIndex
while(all(ind > 0 for ind in mainTupleIndex)):
neighborsIndexes = list(neigh(mainTupleIndex));
#generating neighbour indexes with main tuple index in form of list
anyOperation = False;
for tupleIndex in neighborsIndexes:
current = inverseDistances[mainTupleIndex];
if(current == inverseDistances[tupleIndex]): # comparing indexes in main tuple index and inverse #distance tuple index
mainTupleIndex = tupleIndex;
anyOperation = True;
break;
if(not anyOperation): # if anyoperation is False then we are generating sunString
subString += str(sqs[0][mainTupleIndex[0] - 1]);
mainTupleIndex = neighborsIndexes[-1];
return subString[::-1]; # reversing resulted string
sequences = ["83217", "8213897", "683147"]
print(longestCommonSubSequenceOfN(sequences)); #837
