Reversal Distance

https://rosalind.info/problems/rear/

ROSALIND | Reversal Distance

Problem

A reversal of a permutation creates a new permutation by inverting some interval of the permutation; (5,2,3,1,4)(5,2,3,1,4), (5,3,4,1,2)(5,3,4,1,2), and (4,1,2,3,5)(4,1,2,3,5) are all reversals of (5,3,2,1,4)(5,3,2,1,4). The reversal distance between two permutations ππ and σσ, written drev(π,σ)drev(π,σ), is the minimum number of reversals required to transform ππ into σσ (this assumes that ππ and σσ have the same length).

Given: A collection of at most 5 pairs of permutations, all of which have length 10.

Return: The reversal distance between each permutation pair.

Sample Dataset

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

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

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

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

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

Sample Output

9 4 5 7 0

 

 이 문제는 순열의 어느 부분을 임의로 몇 번 역전시켜야 같은 순열이 되는지를 출력하는 문제이다. 필자는 처음에 언뜻보고는 무언가 규칙이 있지 않을까 고민했지만 힌트에 더러운 풀이를 주저하지 말라는 말을 듣고 브루트 포스로 풀어야겠다고 생각했다. 

 먼저 거꾸로 뒤집는 가능한 모든 경우를 리스트로 만드는 함수를 만들었다. 이후 그 리스트 안의 인자를 하나하나 튜플로 변환시켜 집합에 넣어 만약 두 집합의 교집합이 있다면 일치하는 것이 있다는 것이므로 그대로 출력하는 식으로 함수를 만들었다.

 이 문제는 평소 잘 쓰지 않았던 집합을 다루느랴 약간 머리가 아팠다.

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()
            rev_s=s[:i] + r_list + s[j+1:]
            group.append(rev_s)
    
    return group

def reverse_distance(s1,s2,distance):#s1,s2는 세트형식
#&는 교집합이므로 있다면 일치하는 것이 있다
    if s1 & s2:#
        return distance
    new_s1=set()
    for s in s1:#집합에 튜플들
        for i in reverse_group(list(s)):#튜플에 튜플들
            new_s1.add(tuple(i))
    new_s2=set()
    for s in s2:
        for i in reverse_group(list(s)):
            new_s2.add(tuple(i))
    distance+=2#한번에 두번 해서 거리 +2
    if s1 & new_s2:
        return distance-1
    if new_s1 & s2:
        return distance-1
    if new_s1 & new_s2:
        return distance
    
    distance=reverse_distance(new_s1,new_s2,distance)
    return distance


ans=[]
with open(r'파일경로','r') as fi:
    lines = fi.readlines()
for i in range(0,len(lines),3):
    S1=(lines[i].rstrip()).split()
    S2=(lines[i+1].rstrip()).split()
    distance,s1,s2=0,set(),set()
    s1.add(tuple(S1))
    s2.add(tuple(S2))

    d=reverse_distance(s1,s2,distance)
    print(d,end=' ')