An inversion in a sequence is a pair of entries that are out of order. For examp

Question

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 before D; so do characters H and D. 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 (i.e., a string) of uppercase characters A through Z and returns the number of inversions in the sequence. Please use simple python

>>> inversions ('ABBFHDL')

2

>>> inversions('ABCD')

0

>>>inversions('DCBA')

6

Explanation / Answer

def inversions(string):

if(len(string) <= 1):
return 0

count = 0

for i in range(0, len(string)-1):
for j in range(i+1, len(string)):
if(string[i] > string[j]):
count = count + 1

return count

def main():

n = inversions("ABBFHDL")
print("inversions("ABBFHDL"): ", n)

n = inversions("ABCD")
print("inversions("ABCD"): ", n)

n = inversions("CDBA")
print("inversions("CDBA"): ", n)

n = inversions("DCBA")
print("inversions("DCBA"): ", n)

n = inversions("")
print("inversions(""): ", n)

main()

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.