【ROSALIND】【练Python，学生信】39 按顺序排列不同长度的字符串
如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面 谢谢配合~
题目：
排列不同长度的字符串（Organizing Strings of Different Lengths）
Given: A permutation of at most 12 symbols defining an ordered alphabet A and a positive integer n (n≤4).
所给：给出不超过12个字符的集合以及一个不大于4个正整数。
Return: All strings of length at most n formed from A, ordered lexicographically. (Note: As in “Enumerating k-mers Lexicographically”, alphabet order is based on the order in which the symbols are given.).
需得：由A中字符组成的所有长度不超过n的字符串，按照A中给出的顺序进行排列。
测试数据
D N A
3
测试输出
D
DD
DDD
DDN
DDA
DN
DND
DNN
DNA
DA
DAD
DAN
DAA
N
ND
NDD
NDN
NDA
NN
NND
NNN
NNA
NA
NAD
NAN
NAA
A
AD
ADD
ADN
ADA
AN
AND
ANN
ANA
AA
AAD
AAN
AAA
背景
在23 按字母顺序排列的K-mer中，我们已经可以对长度相同的字符串按照字符顺序进行排列。但就像字典中不会只有相同长度的单词，我们不能满足于只排列相同长度的序列。举个例子，假设我们有两个字符串s=s1s2⋯sm和 t=t1t2⋯tn，且m<n。对于t的子串t′=t[1:m]，我们有如下两种情况：
一．若s=t’，则s<Lext，因为s比t短 (即 APPLE<APPLET)。
二．若s≠t’，如果s<Lext’，则s<Lext；若s>Lext’，则s>Lext。（即因为APPL<LexARTS，APPLET<LexARTS）
计算机背景
快速排序是一种利用分治策略的排序算法。所谓分治策略是将原问题不断分解为若干相似但规模更小的问题，以递归的方式解决这些子问题，最后再将子问题的解合并为原问题的解。快速排序的基本思想是选定一个基准值，把序列分为两个部分，一部分都比基准值小，另一部分都比基准值大，再对这两个部分用相同方式进行排序，直到整个序列都有序。具体的解释可阅读这篇博文：https://www.cnblogs.com/liuyicai/p/9985769.html。
思路
我把这道题分为两个部分：首先，我要用枚举的方法得到所有字符在所有所需长度的组合；第二，我要将这些组合按要求进行排序。
第一步我们在23 按字母顺序排列的K-mer已经基本解决了，这里只稍加改动。之前的函数返回的是储存为k-mer的列表，现在只用在最后返回结果的时候把比k-mer短的那些字符串也加到列表里，最后再把1-mer（即原字符集合）也加上即可。
第二部实际就是排序问题，我这里采用了快速排序。网上有大量快速排序的博文和代码，参考即可。要注意的是排序时对每个字符串长度的判断，按照问题中给出的两个情况分析即可。
代码
def perm(c1, c2, k):
"""进行排列的函数"""
i = 0
ls = []
while i < len(c1):
j = 0
while j < len(c2):
ls.append(c1[i] + c2[j])
j += 1
i += 1
i = 2
while i < k:
i += 1
ls = ls + perm(c1, ls, k - 1) # 以递归的方式得到长度不长于k的字符的排列
break
return ls
def compare(c1, c2):
"""比较两个字符串大小的函数"""
for k in range(min(len(c1), len(c2))): # 以循环的方式比较两字符串，为避免超过范围，取短字符串为界
if dic[c1[k]] > dic[c2[k]]: # 比较同一位的字符大小
return 1 # 1代表c1比c2大
elif dic[c1[k]] < dic[c2[k]]:
return 0 # 0代表c1比c2小
if len(c1) > len(c2): # 执行到这里说明长字符子串和短字符相同，则谁短谁小
return 1
else:
return 0
def partition(seq, low, high):
"""进行快速排序的分组函数"""
pivot = seq[low] # pivot是基准值，把比它小的小的放在它左边，反之放右边
while low < high:
while low < high and compare(seq[high], pivot) == 1:
high -= 1
seq[low] = seq[high]
while low < high and compare(seq[low], pivot) == 0:
low += 1
seq[high] = seq[low]
seq[low] = pivot
return low
def quickSort(seq, low, high):
"""快速排序函数"""
if low < high:
pi = partition(seq, low, high)
quickSort(seq, low, pi - 1) # 采用分治策略，不断划分为子序列进行排序
quickSort(seq, pi + 1, high)
return seq
f = open('input.txt', 'r')
lines = f.readlines()
f.close()
N = int(lines[1])
symbols = lines[0].replace('\n','')
symbols = symbols.split(' ')
# symbols = [''] + symbols
dic = {} # 建立一个字典，目的是存储每个字符和其顺序的关系
n = 1
for i in symbols:
dic[i] = n
n += 1
res = perm(symbols, symbols, N) # 用res接收返回的字符串
res = symbols + res # 再把1-mer加到res前
res = quickSort(res, 0, len(res) - 1) # 快速排序
f = open('output.txt', 'a')
for i in res:
f.write(i)
f.write('\n')
f.close()
