Counting inversions in a string

Question

im new to python taking my first class and im doing very well so far, but this problem is killing me, I would appriciate any help i can get.

Problem:

An inversion in a sequence is a pair of entries that are out of order. For example, the characters F and D form an inversion in string 'ABBFHDL', because F appears earlier in the string but later in the alphabet. Characters H and D also form an inversion. The total number of inversions in a sequence, i.e. the number of pairs that are out of order, is a measure of how unsorted the sequence is. the total number of inversions in 'ABBFHDL' is 2. Implement function inversions() that takes a sequence (string) of upper case characters A through Z and returns the number of inversions in the sequence.

what I got so far is the following:

    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

and its not far enough down the rabit hole to get good partial credits :(

and this gives me 1 so this is not correct (should be 2).

what im wondering about, and this is a big hurdle right now, is how to write the code in order to achieve this: # for each index j that is greater than i

i have tried several codes but i dont get it to work, i have tried these:

    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()

What i can't achieve is to get the function iterate over every possible pair in the sequence (string).

(i.e AA, AB, AB, AF, AH, AD, AL, BB, BB, BF, BH, BD, BL, (none of these would render a count - but when the iteration reach F there would be an inversion count for FD and then for HD, hence the answer 2)

I just cant get there with my code.

Answer 1

Revised code

this should work

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)

Answer 2

Here's a way to get all the letter pairs:

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

I'll leave the counting part to you!

Answer 3

Now what I'm offering is not nice code, but it might still be educational.

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

Does exactly what you specified and is a one-liner. I wrote this for a code-golf challenge once.

You can even nicen it up a bit by using itertools:

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

You can use these lambda functions like you would use any other function:

In [32]: inv('ABBFHDL')
Out[32]: 2