| [ QuizWit ] in KIDS 글 쓴 이(By): jccha (jccha) 날 짜 (Date): 2001년 8월 5일 일요일 오전 11시 54분 52초 제 목(Title): Re: 저도 순열과 관계된 문제... 앞의 분들 말씀대로 문제는 결국 { (a_1,...,a_{n-1}) | 0 <= a_i <= n-i } 과 the set of n-permutations 간의 bijection을 찾는 것인데, 이 set의 크기가 너무 커서 mapping table (O(n!)-space) 을 쓰기에는 적합하지 않고, 적당한 computable binjection을 찾는 것이 필요합니다. 이런 것들 중 잘 알려진 하나는 permutation과 그 inversion table간의 상호 변환 방법입니다. 아무 combinatorics 책에 보면 나올 겁니다. 양방향 변환 모두 O(n^2)에 가능할 겁니다. sharper님이나 ash님의 방법은 기본적으로 이것과 같은 아이디어로 보입니다. Quiz: inversion table을 약간 변형시켜 잘 생각하면 양방향 변환 모두 O(n)-time, O(n)-space에 할 수 있는 방법도 있습니다. |