前言：
如何求最长公共子序列的长度相信大家都很熟悉，但是如何求出最长公共子序列的所有可能结果呢？接下来，就让小编带大家了解一下小编使用的方法吧。
问题描述：
我们先给定两个序列，以这个为例，求出它们最长公共子序列的所有可能，并储存入列表后输出。
s1 = '357486782'
s2 = '13456778'
基本流程：
阶段一：找出最长公共子序列长度。
现在我们先研究如何找出最长公共子序列长度的问题，我们先把s1和s2的内容排成一行和一列，组成个图表，并在第一个留空，然后将留空的行列全部填上0。
方法出自动态规划 最长公共子序列 过程图解_hrn1216的博客-CSDN博客_最长公共子序列
思路一：
1.分别以s1和s2的序列做横纵坐标，在第一行第一列填满0，如图所示。
2.遍历s2的所有元素，每个元素都匹配一遍s1的所有元素。
2.1两者不同则取左边第一个数和上面第一个数中最大的一个填入。
2.2 两者相同则在左上角数的基础上加1
2.3 以此方式填满列表，并把以2.2方法得到的数打上黄色标记。
代码初步实现：
为了方便索引，我们先设置四个变量名用以储存，其所代表的内容如图所示。
lx，ly，ix，iy四个变量名
现在我们整理一下上述的方法，并将其对应的代码实现写出来，如图所示。
代码完整实现：
阶段二：找出所有的最长公共子序列。
思路二：
1.在思路一中打上黄色标记的数，以(目前最长公共子序列长度，iy，ix)的方式建立对应的辅助坐标。
辅助坐标的意义：
判断两个数能不能出现在同一个最长公共子序列里，在此我们基于一个假设：
若有两个结果数，A-（a1，iy1，ix1），B-（a2，iy2，ix2）
当iy2>iy1, ix2>ix1且a2 = a1+1时，可有“AB“序列
（这个假设我自己想的，可能不对，如有问题还请大家指出）
代码实现：
2.将辅助坐标排序，这里使用了快速排序算法。
代码实现：
使用算法排序后打印出来的结果：
3.处理结果（n_arr）：
最长公共子序列长度为5，意味着一个最长公共子序列有五个位置，按照这个位置
将结果数和坐标进行分组，将列表内的结果数和坐标进行分离，分别储存在两个列表里。
代码实现：
获得的结果
4.进行三层嵌套的for循环
第一层遍历l_arr，获得元素
第二层遍历l_arr遍历到的的当前元素，
第三次遍历l_arr的当前元素的下个元素。
从五个组中分别给五个位置取数
5.将坐标转换成字符串，这个代码得出的结果可能会有重复，因此转换成字符串后再用集合去重
完整代码：
s1 = '357486782'
s2 = '13456778'
lx = []
ly = []
for i in range(len(s1)+1):
lx.append(0)
ly.append(lx)
# 2.进行字符匹配
iy = 0 # 记录横向列表的序数
# 建立两个列表，一放结果数，二放结果数的一维数组
n_arr = [] # 结果数和对应的一维数组-(序数，纵坐标，横坐标)
dic_n_arr = {} # 以字典的形式存储结果数和对应的一维数组-(序数，纵坐标，横坐标)
for y in range(len(s2)):
iy += 1
ix = 0 # 记录横向列表内每个元素的序数
ly.append([0])
for x in range(len(s1)):
ix += 1
if s2[y] != s1[x]:
val = max(ly[iy][ix-1], ly[iy-1][ix])
else:
val = ly[iy-1][ix-1]+1
n_arr.append([s2[iy - 1], (val, iy, ix)])
dic_n_arr[(val, iy, ix)] = s2[iy - 1]
ly[iy].append(val)
print('数组建立结束')
# 目的：输出所有可能的最长子序列
# 1.建两个列表，一放结果数，二放结果数的一维数组
# 2.排序 --- 用快速排序的算法进行迭代
def quicksort_b(arr): # 列表 l_res 为参
if len(arr) <= 1:
return arr
else:
prvot = arr[0][1][0]
# 以目标为要求，从arr里挑出符合要求的数。
l = [i for i in arr[1:] if i[1][0] <= prvot] # 遍历除第一个以外的数，小的放左边
r = [i for i in arr[1:] if i[1][0] > prvot]
l = quicksort_b(l)
r = quicksort_b(r)
return l+[arr[0]]+r
print(n_arr)
print('数组排序结束')
n_arr = quicksort_b(n_arr)
print(n_arr)
l_n = [] # 存放结果的列表
l_arr = [] # 存放坐标的列表
for i in range(len(n_arr)):
if n_arr[i][1][0] > len(l_n):
l_n.append([])
l_arr.append([])
l_n[-1].append(n_arr[i][0])
l_arr[-1].append(n_arr[i][1])
print(l_n)
print(l_arr)
last_arr = [] # 存放最后结果的列表
for a in range(len(l_arr)):
if a == 0:
for b in l_arr[a]: # 遍历las_a里第一个[]的所有元素
last_arr.append([b])
else:
ll = len(last_arr) # lis是内含一层列表的列表，c即为一个列表,里面储存结果数
for b in l_arr[a]: # las_a是内含一层的列表，las_a[a]为一个列表，b为一个元素
#print('b:', b)
for c in range(ll): # ll是最外列表的索引值，c即为一个列表,里面储存结果数
c = last_arr[c] # c即为一个列表,里面储存结果数
#print('c:',c)
if c[-1][1] < b[1] and c[-1][2] < b[2]:
h = c[:] # 将c里除最后一个元素外，全复制下来
h.append(b)
last_arr.append(h)
del last_arr[:ll]
print('数组出结果结束')
# print('n_arr:', n_arr) # 将元素(n)和对应的坐标(arr)合并，方便排序
# print('dic_n_arr:', dic_n_arr) # 将元素(n)和对应的坐标(arr)合并，方便查找
# print('l_n:', l_n) # 存放结果元素的列表
# print('l_arr:', l_arr) # 存放结果元素对应的坐标的列表
# print('last_arr:', last_arr) # 存放最后结果的列表，以坐标形式
# 将坐标转换成具体字符
last_n = [] # 存放最后结果的列表，以具体元素形式
for i in last_arr:
lis = []
for j in i:
lis.append(dic_n_arr[j])
last_n.append(lis)
last_s = [] # 存放最后结果的列表，以字符串形式
for i in last_n:
newi = ''.join(i)
last_s.append(newi)
# 删除重复元素
last = set(last_s)
print('所有可能的最长公共子序列：', last)
