| [ QuizWit ] in KIDS 글 쓴 이(By): ash (無味乾燥) 날 짜 (Date): 2001년 8월 3일 금요일 오후 11시 35분 31초 제 목(Title): Re: 저도 순열과 관계된 문제... 저도 생각해 봤는데.. 기본적인 아이디어는 이렇습니다. n개의 자료들을 정렬했을 때, 왼쪽에서 부터 a_0, a_1, ..., a_n-1 이라고 하면, a_i 로 시작하는 순열의 갯수는 (n-2)! 개 입니다. a_i 로 시작하는 순열에 (i-1)*(n-2)! ~ i*(n-2)! 의 번호를 부여합니다. 자료의 개수가 n-1, ..., 1 일 때 까지 재귀적으로 적용하면 모든 순열에 서로 다른 번호를 부여할 수 있고, 번호에서 순열을 만들어 낼 수도 있습니다. .......................... 대상 n개를 0 ~ n-1 사이의 숫자와 1:1 대응 관계를 만듭니다. (mapping table 을 만듭니다.) 이 테이블은 [순열->번호] [번호->순열] 모두에 사용됩니다. (당연한가?) [순열->번호] INPUT : 대상 n개로 이루어진 순열 OUTPUT : number 초기화 : 입력된 순열에 있는 자료들을 mapping 된 수들로 변경. number = 0 i = n 알고리즘: 1. i = i - 1 2. 순열의 첫째 수 : m 3. number = number + m * i! 4. 순열에서 m을 제거하고, m 보다 큰 수는 모두 1 감소시킴. 5. i > 1 이면 1. 로, 아니면 종료 ....................................... 예를들어 {23, 32, 8, 15} 라는 자료가 있을 때, 크기 순으로 mapping table 을 만들면, { (8,0), (15,1), (23, 2), (32, 3) } 이므로 {23, 32, 8, 15} -> {2, 3, 0, 1} 2 * 3! = 12 { 3, 0, 1 } -> {2, 0, 1} 2 * 2! = 4 { 2, 0, 1 } -> {0, 1} 0 * 1! = 0 각 단계에서 나온 12, 4, 0 을 합하면 16 입니다. ............................... [번호->순열] INPUT : number OUTPUT : 순열 초기화 : i = n 알고리즘: 1. i = i - 1 2. m = number / i! 3. number = number % i! ( = number - m * i! ) 4. m을 순열에 추가, 만약 m과 같은 수가 이미 순열에 있으면 m을 1증가시킴. m을 증가시켰을 때에도 같은 수가 이미 순열에 있으면, 중복되지 않을 때까지 1씩 증가시킴. 5. i > 1 이면 1. 로, 아니면 6.으로 6. number 를 순열에 추가. 추가할 때 4번과 동일한 방법 사용. 7. mapping table 을 이용해서 원래의 자료로 변경 ................................ 4개의 자료에 대해서 16이라는 번호가 주어지면 16 / 3! : 몫 2 나머지 4 --> 2 4 / 2! : 몫 2 나머지 0 --> 3 0 / 1! : 몫 0 나머지 0 --> 0, 1 {2, 3, 0, 1} 을 mapping table 을 이용해서 변환 {23, 32, 8, 15} |