【ROSALIND】【練Python，學(xué)生信】39 按順序排列不同長度的字符串
如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】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個正整數(shù)。
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中給出的順序進(jìn)行排列。
?
測試數(shù)據(jù)
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中，我們已經(jīng)可以對長度相同的字符串按照字符順序進(jìn)行排列。但就像字典中不會只有相同長度的單詞，我們不能滿足于只排列相同長度的序列。舉個例子，假設(shè)我們有兩個字符串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）
?
計算機(jī)背景
??? ????快速排序是一種利用分治策略的排序算法。所謂分治策略是將原問題不斷分解為若干相似但規(guī)模更小的問題，以遞歸的方式解決這些子問題，最后再將子問題的解合并為原問題的解。快速排序的基本思想是選定一個基準(zhǔn)值，把序列分為兩個部分，一部分都比基準(zhǔn)值小，另一部分都比基準(zhǔn)值大，再對這兩個部分用相同方式進(jìn)行排序，直到整個序列都有序。具體的解釋可閱讀這篇博文：https://www.cnblogs.com/liuyicai/p/9985769.html。
?
思路
????????我把這道題分為兩個部分：首先，我要用枚舉的方法得到所有字符在所有所需長度的組合；第二，我要將這些組合按要求進(jìn)行排序。
????????第一步我們在23 按字母順序排列的K-mer已經(jīng)基本解決了，這里只稍加改動。之前的函數(shù)返回的是儲存為k-mer的列表，現(xiàn)在只用在最后返回結(jié)果的時候把比k-mer短的那些字符串也加到列表里，最后再把1-mer（即原字符集合）也加上即可。
????????第二部實際就是排序問題，我這里采用了快速排序。網(wǎng)上有大量快速排序的博文和代碼，參考即可。要注意的是排序時對每個字符串長度的判斷，按照問題中給出的兩個情況分析即可。
?
代碼
def perm(c1, c2, k):
??? """進(jìn)行排列的函數(shù)"""
??? 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):
??? """比較兩個字符串大小的函數(shù)"""
??? for k in range(min(len(c1), len(c2))): # 以循環(huán)的方式比較兩字符串，為避免超過范圍，取短字符串為界
??????? 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): # 執(zhí)行到這里說明長字符子串和短字符相同，則誰短誰小
??????? return 1
?? ?else:
??????? return 0
def partition(seq, low, high):
??? """進(jìn)行快速排序的分組函數(shù)"""
??? pivot = seq[low] # pivot是基準(zhǔn)值，把比它小的小的放在它左邊，反之放右邊
??? 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):
??? """快速排序函數(shù)"""
??? if low < high:
??????? pi = partition(seq, low, high)
??????? quickSort(seq, low, pi - 1) # 采用分治策略，不斷劃分為子序列進(jìn)行排序
??????? 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 = {} # 建立一個字典，目的是存儲每個字符和其順序的關(guān)系
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()
