Sorting by Reversals

https://rosalind.info/problems/sort/

ROSALIND | Sorting by Reversals

Problem

A reversal of a permutation can be encoded by the two indices at the endpoints of the interval that it inverts; for example, the reversal that transforms (4,1,2,6,3,5)(4,1,2,6,3,5) into (4,1,3,6,2,5)(4,1,3,6,2,5) is encoded by [3,5][3,5].

A collection of reversals sorts ππ into γγ if the collection contains drev(π,γ)drev(π,γ) reversals, which when successively applied to ππ yield γγ.

Given: Two permutations ππ and γγ, each of length 10.

Return: The reversal distance drev(π,γ)drev(π,γ), followed by a collection of reversals sorting ππ into γγ. If multiple collections of such reversals exist, you may return any one.

Sample Dataset

1 2 3 4 5 6 7 8 9 10
1 8 9 3 2 7 6 5 4 10

Sample Output

2
4 9
2 5

 

 이 문제는 reversal distance에서 그 경로까지 출력하는 문제이다. 필자는 개인적으로 reversal distance를 구하는 것이 어려워서 이 문제도 상당히 어려웠다.

 이 문제를 푸는 법은 먼저 reversal distance에서 구하듯이 동시에 뒤집으면서 진행한다. 이때 무엇을 무엇으로 뒤집었는지를 통째로 딕셔너리에 저장한다. 이후 중간에 만나는 그 배열을 구하면, 통로를 저장한 딕셔너리의 리스트를 되짚어보며 그 경로를 구한다. 

def reverse_group(s):#거꾸로 하기
    group=[s]
    for i in range(len(s)):
        for j in range(i+1,len(s)):
            r_list=s[i:j+1]
            r_list.reverse()
            group.append(s[:i] + r_list + s[j+1:])
    
    return group

def reverse_distance(s1,s2,distance,s1_s2_path,s2_s1_path,meet_rev):
    if s1 & s2:
    	meet_rev = s1&s2
        return s1_s2_path,s2_s1_path,meet_rev,distance
    new_s1=set()
    s1_s2={}#경로 저장용
    for s in s1:
            reverse_array=list(reverse_group(list(s)))
            s1_s2[s] = reverse_array
            for r in reverse_array:
                new_s1.add(tuple(r))
    s1_s2_path.append(s1_s2)#경로 저장한 함수를 통째로 저장

    new_s2=set()
    s2_s1={}
    for s in s2:
        reverse_array=list(reverse_group(list(s)))
        s2_s1[s] = reverse_array
        for r in reverse_array:
            new_s2.add(tuple(r))
    s2_s1_path.append(s2_s1)

    distance+=2
    #만나는 구간은 통째로 반환 
    if s1 & new_s2:
        meet_rev=list(s1&new_s2)
        return s1_s2_path,s2_s1_path,meet_rev,distance-1
    if new_s1 & s2:
        meet_rev = list(new_s1&s2)
        return s1_s2_path,s2_s1_path,meet_rev,distance-1
    if new_s1 & new_s2:
        meet_rev = list(new_s1&new_s2)
        return s1_s2_path,s2_s1_path,meet_rev,distance
    
    s1_s2_path,s2_s1_path,meet_rev,distance=reverse_distance(new_s1,new_s2,distance,s1_s2_path,s2_s1_path,meet_rev)
    return s1_s2_path,s2_s1_path,meet_rev,distance

def get_invert(a,b):#어떻게 뒤집혔는지를 구하기
     a_reverse=[]
     for i in range(len(a)-1):
          for j in range(i+1,len(a)):
               a_reverse = a[:i] + a[i:j+1][::-1] + a[j+1:]
               if a_reverse == b:
                    return i+1,j+1

def get_sort(s1_s2_rev,meet_rev,s2_s1_rev):
    cols=[]
    for l in meet_rev:#여러개의 만남 중
        col=[]
        current_array = list(l)#가야할 곳
        for reversal_path in s1_s2_rev[::-1]:
            for k,v in reversal_path.items():
                if current_array in v:
                    i,j = get_invert(list(k),current_array)
                    col.append([i,j])
                    current_array = list(k)
                    break
        col = col[::-1]
        current_array = list(l)
        for reversal_path in s2_s1_rev[::-1]:
             for k,v in reversal_path.items():
                  if current_array in v:
                    i,j = get_invert(list(k),current_array)
                    col.append([i,j])
                    current_array = list(k)
                    break
        cols.append(col)
    return cols

a=input().split()
b=input().split()

distance,s1,s2=0,set(),set()
s1.add(tuple(a)),s2.add(tuple(b))
s1_s2_rev=[]
s2_s1_rev=[]
meet_rev=[]

s1_s2_rev,s2_s1_rev,meet_rev,distance = reverse_distance(s1,s2,distance,s1_s2_rev,s2_s1_rev,meet_rev)
a_collection = get_sort(s1_s2_rev,meet_rev,s2_s1_rev)

print(distance)
for i in a_collection[0]:
     print(i[0],i[1])