| [ QuizWit ] in KIDS 글 쓴 이(By): shaper (나~랑께롱!) 날 짜 (Date): 2001년 8월 3일 금요일 오후 08시 35분 40초 제 목(Title): Re: 저도 순열과 관계된 문제... 제 생각에 원래의 문제는 이런 것을 원하는 것이 아닌가 생각합니다. 1) 임의의 number (0<=number<n!)로부터 그에 해당하는 순열을 알아낸다. 2) 임의의 순열로부터 그에 해당하는 number (0<=number<n!)를 알아낸다. 님의 질문을 보고 그냥 제 나름대로 생각해본건데 이런 방법은 어떨까요? 기본 아이디어는 간단합니다. 특이한 숫자 n_(2) ... n_(m) ... n_(n) 를 생각해봅시다. 이 숫자는 각 자리수마다 서로 다른 진수법을 따릅니다. 즉, 앞에서부터 m-1번째 자리값인 n_(m)는 m진수법에 해당하는 값으로서 0부터 m-1까지의 m가지의 값을 가집니다. 이를 10진법으로 환산한 숫자 "number"는 다음과 같습니다. n number = Sigma n_(m) * n!/m! m = 2 이렇게 하면 숫자 number는 0 <= number < n! 의 범위를 갖게 됩니다. 이제 이 특이한 숫자 n_(2) ... n_(m) ... n_(n) 와 순열을 대응시키는 방법만 생각하면 됩니다. 다음은 그 방법의 설명입니다. 아래에 언급되는 숫자는 모두 보통의 10진수 숫자를 나타내고, %는 "나머지", /은 "몫"을 의미합니다. [숫자->순열] 초기화 : a) 먼저 대상 n개의 순서를 정하여 왼쪽부터 순서대로 나열하고 왼쪽부터 0, 1, 2, ...., n-1의 n진수의 한자리수에 해당하는 번호를 매깁니다. 이를 편의상 "대상목록"이라하죠. 이들의 순서는 바뀌지 않으며, 대신 한 대상이 사용되고 나면 목록에서 빠집니다. b) number = 주어진 숫자(물론 0부터 n!-1까지의 숫자겠죠?) c) m = n 1) n_(m) = number % m 에 해당하는 대상목록에서의 대상이 순열의 m번째 위치의 대상입니다. 2) number = number / m m = m - 1 3) 해당 대상을 대상목록에서 제거하고 다시 왼쪽부터 0, 1, 2, ...., m-1의 m진수의 한자리수에 해당하는 번호를 매깁니다. 4) m > 1 이면 1)로 가고, m = 1 이면 끝 [순열->숫자] 초기화 : a) 대상목록을 비운 후 순열의 첫번째 위치의 대상만을 대상목록에 넣는다. b) number = 0 c) m = 1 1) m = m + 1 2) 순열의 m번째 위치의 대상을 대상목록에 집어 넣되 [숫자->순열]에서의 초기화에 사용한 순서가 깨지지 않게 끼워넣은 후에, 왼쪽부터 0, 1, 2, ...., m-1의 m진수의 한자리수에 해당하는 번호를 매깁니다. 3) n_(m) = 방금 추가된 대상의 대상목록에서의 대응되는 번호 number = number * m + n_(m) 4) m<n 이면 1)로 가고, m=n 이면 끝 P.S. : 물론 실제로 coding할 때는 대상목록에 넣고 빼는 것을 그대로 구현하는 대신에 대상목록배열에 각 대상에 해당하는 m진수 자리수값을 상황에 맞게 0부터 m-1까지의 숫자를 적절히 변경해주면 되겠죠. 대상목록에서 빠진 대상은 -1로 표시를 해주고... |