0

我是 python 新手，我上了第一堂课，到目前为止我做得很好，但是这个问题让我很生气，我会感谢我能得到的任何帮助。

问题：

序列中的反转是一对乱序的条目。例如，字符 F 和 D 在字符串 'ABBFHDL' 中形成反转，因为 F 在字符串中出现较早，但在字母表中较晚。字符 H 和 D 也形成反转。序列中反转的总数，即乱序对的数量，是序列未排序程度的量度。'ABBFHDL' 中的反转总数为 2。实现函数 inversions()，它采用大写字符 A 到 Z 的序列（字符串）并返回序列中的反转数。

到目前为止我得到的是以下内容：

    def inversions(s):
        count = 0
        for i in range(len(s)):          # for each index i
            for j in range(len(s)):      # for each index J
                if s[j]>=s[i]:           # compare string[i] and string[j]
                    count += 0

                else:
                    count +=1
                    return count

而且它还不够深入，无法获得良好的部分学分:(

这给了我 1 所以这是不正确的（应该是 2）。

我想知道的是，现在这是一个很大的障碍，是如何编写代码来实现这一点：#对于每个大于 i 的索引 j

我已经尝试了几个代码，但我没有让它工作，我尝试了这些：

    for j in range(len(s)>i):        # the result i get is 1
    for j in range(len(s)<i):        # the result i get is 'blank
    for j in range(len(s)>s[i]):    # the result i get is this error message : 

    for j in range(len(s)>s[i]):
    TypeError: unorderable types: int() > str()

我无法实现的是让函数迭代序列（字符串）中的每个可能对。

（即 AA、AB、AB、AF、AH、AD、AL、BB、BB、BF、BH、BD、BL，（这些都不会产生计数 - 但是当迭代达到 F 时，会有一个反转计数FD，然后是 HD，因此答案是 2)

我只是无法使用我的代码到达那里。

4

3 回答 3

2

修改后的代码

这应该工作

def inversions(s):
        count = 0
        for i in range(len(s)-1):
            for j in range(i+1,len(s)):
                if s[i] > s[j]:
                    print(s[i],s[j])
                    count +=  1
                    break
#remove 'break' if you want to count every possible 
#out of order pair for a particular character in the string
        print(count)
于 2013-05-17T17:36:18.050 回答
1

这是获取所有字母对的方法：

for i in range(len(s)):
    for j in range(i + 1, len(s)):
        print s[i], s[j]

我将把计数部分留给你！

于 2013-05-17T17:52:01.813 回答
0

现在我提供的不是很好的代码，但它可能仍然具有教育意义。

inv = lambda w:sum([sum([w[i]>w[j] for j in range(i+1,len(w))]) for i in range(len(w))])

完全按照您指定的方式进行操作，并且是单行的。我曾经为代码高尔夫挑战写过这个。

您甚至可以使用 itertools 对其进行微调：

from itertools import combinations
inv = lambda w:sum([w[i]>w[j] for i,j in combinations(range(len(w)),2)])

您可以像使用任何其他函数一样使用这些 lambda 函数：

In [32]: inv('ABBFHDL')
Out[32]: 2
于 2015-08-12T13:18:39.407 回答