| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2001년 8월 11일 토요일 오후 04시 08분 21초 제 목(Title): Re: 저도 순열과 관계된 문제... 어렵게 코드를 들이밀지 말고요.. --; 예로 다음 순열이 있다고 합시다: [1 4 2 3] 다음과 같은 중간 encoding을 하나 만듭니다. 각 자리에 자신의 앞에 자기보다 작은 숫자가 몇개 있는지를 적습니다. [0 1 1 2] 가 되죠? 제일 앞 자리는 무조건 0, 두번째 자리는 0 아니면 1, ... n번째 자리는 0에서 n-1 사이의 값이 됩니다. 이제 이 숫자를 가지고 정수 하나를 만듭니다. 0*0! + 1*1! + 1*2! + 2*3! = 0 + 1 + 2 + 12 = 15 이런 식으로 하면 임의의 순열에서 0 ~ n!-1 사이의 값을 얻을 수 있습니다. (1:1 대응이라는 것도 어렵지 않습니다.) 이제 거꾸로 원래 순열을 얻어내는 방법은.. 15를 차례대로 2, 3, 4, ... 로 나누면서 나머지를 얻습니다. 15 / 2 = 7 나머지 1 7 / 3 = 2 나머지 1 2 / 4 = 0 나머지 2 맨 앞에 0 하나를 붙이고 위에서부터 적으면 [0 1 1 2] 아까의 중간 encoding이 되죠? 여기서 원래 순열로 만드는 부분은 남겨둡니다. (어렵지 않습니다.) -- 박.. |