길이가 m인 문자열이 있고 이 문자열에 소문자만 포함되어 있다고 가정하면 사전순으로 문자열의 n번째 순열을 찾아야 합니다.
따라서 입력이 string ="pqr", n =3과 같으면 모든 순열이 [pqr, prq, qpr, qrp, rpq, rqp]이므로 출력은 "qpr"이고 정렬된 순서입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
MAX_CHAR :=26
-
MAX_FACT :=20
-
factorials :=MAX_FACT 크기의 배열
-
계승[0] :=1
-
범위 1에서 MAX_FACT까지의 i에 대해 수행
-
계승[i] :=계승[i - 1] * i
-
-
size :=문자열의 크기
-
발생 :=MAX_CHAR 크기의 배열, 0으로 채움
-
범위 0에서 크기까지의 i에 대해
-
발생[(문자열[i])의 ASCII - ('a')의 ASCII ] :=발생[(문자열[i])의 ASCII - ('a')의 ASCII ] + 1
-
-
res :=MAX_CHAR
크기의 배열 -
합계 :=0, k :=0
-
합계가 n과 같지 않은 동안 수행
-
합계 :=0
-
0에서 MAX_CHAR 범위의 i에 대해 수행
-
발생[i]이 0과 같으면
-
다음 반복으로 이동
-
-
발생[i] :=발생[i] - 1
-
temp_sum :=계승[크기 - 1 - k]
-
0에서 MAX_CHAR 범위의 j에 대해 수행
-
temp_sum :=temp_sum / factorials[occurrence[j]] (정수 나누기)
-
-
합계 :=합계 + temp_sum
-
합계>=n이면
-
res[k] :=ASCII 코드의 문자(i + ASCII of('a'))
-
n :=n - 합계 - temp_sum
-
k :=k + 1
-
루프에서 나오다
-
-
합계
-
발생[i] :=발생[i] + 1
-
-
-
-
나는 :=MAX_CHAR-1
-
k <크기 및 i>=0인 동안 수행
-
발생[i]이 0이 아닌 경우
-
res[k] :=ASCII 코드의 문자(i + ASCII of('a'))
-
발생[i] :=발생[i] - 1
-
나는 :=나는 + 1
-
k :=k + 1
-
-
나는 :=나는 - 1
-
-
인덱스 0에서 (k - 1)까지의 res에서 make 문자열을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
factorials[0] = 1
for i in range(1, MAX_FACT):
factorials[i] = factorials[i - 1] * i
size = len(string)
occurrence = [0] * (MAX_CHAR)
for i in range(0, size):
occurrence[ord(string[i]) - ord('a')] += 1
res = [None] * (MAX_CHAR)
Sum = 0
k = 0
while Sum != n:
Sum = 0
for i in range(0, MAX_CHAR):
if occurrence[i] == 0:
continue
occurrence[i] -= 1
temp_sum = factorials[size - 1 - k]
for j in range(0, MAX_CHAR):
temp_sum = temp_sum // factorials[occurrence[j]]
Sum += temp_sum
if Sum >= n:
res[k] = chr(i + ord('a'))
n -= Sum - temp_sum
k += 1
break
if Sum < n:
occurrence[i] += 1
i = MAX_CHAR-1
while k < size and i >= 0:
if occurrence[i]:
res[k] = chr(i + ord('a'))
occurrence[i] -= 1
i += 1
k += 1
i -= 1
return ''.join(res[:k])
n = 3
string = "pqr"
print(get_nth_permute(string, n)) 입력
"pqr"
출력
qpr