Question

using python

One measure of “unsortedness” in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence “DAABEC”, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence “AACEDGG” has only one inversion (E and D)--it is nearly sorted--while the sequence “ZWQM” has 6 inversions. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

So in the sequence 2, 4, 1, 3, 5, there are three inversions (2, 1), (4, 1), (4, 3).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' (lowest inversions) to ``least sorted'’ (highest inversions). All the strings are of the same length.

Input: These are m character sequences given each of fixed length. If the input is “#”, stop the input.

Output: Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. If two or more strings are equally sorted, list them in the same order they are in the input file.

Sample Input: AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT

Sample Output: CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA

Answer 1

Please let me know if anything is required. Please follow the indentation as shown in the screenshot.

Code:

import collections
DNA=[] #list to store the strings
m=input("Enter the length of each string : ") #taking the string length from the user
s=input("Enter the string continue or # to stop : ") #taking the string from the user

#condition to continue or stop taking the input
while(s!='#'):
DNA.append(s) #appending the strings into the list
s=input("Enter the string continue or # to stop : ")

inversion={} #dictornary to store the the inversions values

#loop to calculate the inversions
for i in DNA:
c=0
for k in range(int(m)):
for j in range(int(m)):
if(i[k]>i[j] and k<j):
c=c+1
inversion[i]=c
  

#sorting the inversions dictornary according to values
inversion_sorted = (sorted(inversion.items(), key = lambda kv:(kv[1], kv[0])))   

#printing the results from most sorted to least sorted
print("\nstrings arranged from most sorted to least sorted ")
for data in inversion_sorted:
print(data[0])

Code Screenshot :

Test case :