Python入门习题（63）——OpenJudge百练习题：DNA排序

题目描述

来源
OpenJudge网站 – 百练习题集-第1007号习题
建议学编程的人士利用好这个网站。

总时间限制: 1000ms 内存限制: 65536kB

描述
现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。
逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。

输入
第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0<m<=100)表示字符串数量

第2至m+1行：每行是一个长度为n的字符串
输出
按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。
样例输入
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
样例输出
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

解题思路

1. 输入m个DNA字符串，依次存入dnas列表中。
2. 按DNA字符串逆序对数目，从小到大排序。这一步通过调用列表的sort方法做到的。sort方法采用的排序算法是稳定的，能保证对于逆序对数目相同的DNA串，按输入顺序输出。排序算法分稳定的和不稳定的两种，详情参阅各种排序算法比较(1):稳定性。
3. 如何求出DNA串的逆序对数目？做法是，对于第 i 个字符（i = 1, 2, …, n-1），与其后的字符逐个比较，发现逆序对，则增1。这里，n是DNA串的长度。
4. 第三步采用的算法的时间开销级别是O(n²) 。由于n小于等于50，m小于等于100，程序运行不会超过1000ms这一时间限制。

参考答案

#DNA字符串dna_str有多少个逆序对
def reverse_count(dna_str):
    count = 0
    for i in range(len(dna_str) - 1):
        for j in range(i + 1, len(dna_str)):
            if dna_str[i] > dna_str[j]:
                count += 1
    return count
#测试reverse_count正确性的语句：
# assert reverse_count("CA") == 1
# assert reverse_count("AC") == 0
# assert reverse_count("CAA") == 2
# assert reverse_count("TCAA") == 5
# assert reverse_count("A") == 0
# assert reverse_count("ACGT") == 0
# assert reverse_count("TGCA") == 3 + 2 + 1

n, m = [int(s) for s in input().split()]
dnas = [input() for i in range(m)]

# for dna in dnas:
#     print(dna, ":", reverse_count(dna))

dnas.sort(key=lambda dna: reverse_count(dna))
# dnas.sort(key=reverse_count)  #这样写也可以

for dna in dnas:
    print(dna)

测试用例

1. 题目描述给出的测试用例覆盖了所有DNA串的逆序对数目都不同的情形。

2. 有DNA串的逆序对数目一样多的情形。在这种情形下，先输入的要先输出。这一个测试用例是在题目描述给出的测试用例基础上改的。上一节给出的代码中第21,22行输出出各个DNA串的逆序对数目。
   样例输入
   10 6
   AAACTGAAGG
   TTTTGGCCAA
   TTTGGCCAAA
   GATCAGATTT
   CCCGGGGGGA
   ATCGATGCAT
   样例输出
   AAACTGAAGG
   CCCGGGGGGA
   GATCAGATTT
   ATCGATGCAT
   TTTTGGCCAA
   TTTGGCCAAA

3. m=1的边界情形。
   样例输入
   10 1
   AAACTGAAGG
   样例输出
   AAACTGAAGG

4. 上一节的代码中的第10到16行，用于测试reverse_count函数的正确性。这么做更有针对性，测试用例的输入和期望输出更容易构造。

小结

1. 本文重点关注的一个知识点是Python语言的sort方法，该方法完成列表的排序。sort方法采用的排序算法是稳定的。排序算法分稳定的和不稳定的两种，详情参阅各种排序算法比较(1):稳定性。
2. 上面列出的代码中的第24行，参数“key=lambda dna: reverse_count(dna)”是关键字参数的写法，意思是向形参key传递一个lambda表达式，该表达式的结果用作排序依据。该lambda表达式可以看成一个匿名函数，传入列表元素（是DNA串）给匿名函数的dna参数，返回dna这个DNA串的逆序对数目。关于lambda表达式，可参阅《python – lambda表达式》一文，你也可以在网上搜索到更多的资料。
3. 用assert语句对函数进行正确性测试是一个好做法，值得提倡。