순열과 그 인덱스 배열 간의 관계

https://codeforces.com/contest/1792/problem/D

Problem - D - Codeforces

 

이 문제를 풀다가 이 성질을 알아내서 정리해 두려 한다.

고수들은 이미 다 알고 있었겠지?

 

여기서 순열의 정의는 다음과 같다.

a permutation of length m is a sequence of m distinct integers from 1 to m.

 

결론부터 말하자면, 순열 A의 인덱스 배열을 B라 하면, B도 순열이고, 순열  B의 인덱스 배열은 A이다.

예시를 살펴보면 쉽게 감을 잡을 수 있다.

 

A: 3 4 5 2 1 → B: 5 4 1 2 3

B: 5 4 1 2 3 → A: 3 4 5 2 1 

 

증명은 아직 잘 모르겠다. 생각나면 추가하도록 하겠다.

- 인덱스는 distinct integers from 1 to m의 집합을 뜻하기 때문에 순열임을 알 수 있다.