สมมติว่าเรามีสตริงที่มีความยาว m และสตริงนี้มีเฉพาะตัวพิมพ์เล็ก เราต้องหาการเปลี่ยนลำดับที่ n ของสตริงตามพจนานุกรม
ดังนั้น หากอินพุตเป็นเหมือน string ="pqr", n =3 เอาต์พุตจะเป็น "qpr" เนื่องจากการเรียงสับเปลี่ยนทั้งหมดคือ [pqr, prq, qpr, qrp, rpq, rqp] พวกเขาจะถูกจัดเรียงตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
MAX_CHAR :=26
-
MAX_FACT :=20
-
แฟกทอเรียล :=อาร์เรย์ขนาด MAX_FACT
-
แฟกทอเรียล[0] :=1
-
สำหรับผมอยู่ในช่วง 1 ถึง MAX_FACT ทำ
-
แฟกทอเรียล[i] :=แฟกทอเรียล[i - 1] * i
-
-
size :=ขนาดของสตริง
-
เหตุการณ์ :=อาร์เรย์ขนาด MAX_CHAR เติม 0
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาด ทำ
-
เหตุการณ์[ASCII ของ (สตริง[i]) - ASCII ของ ('a') ] :=การเกิดขึ้น[ASCII ของ (สตริง[i]) - ASCII ของ ('a') ] + 1
-
-
res :=อาร์เรย์ขนาด MAX_CHAR
-
ผลรวม :=0, k :=0
-
ในขณะที่ Sum ไม่เหมือนกับ n ทำ
-
ผลรวม :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง MAX_CHAR ทำ
-
ถ้าเหตุการณ์[i] เท่ากับ 0 แล้ว
-
ไปทำซ้ำต่อไป
-
-
เหตุการณ์[i] :=เหตุการณ์[i] - 1
-
temp_sum :=แฟกทอเรียล[ขนาด - 1 - k]
-
สำหรับ j ในช่วง 0 ถึง MAX_CHAR ทำ
-
temp_sum :=temp_sum / factorials[occurrence[j]] (การหารจำนวนเต็ม)
-
-
ผลรวม :=ผลรวม + temp_sum
-
ถ้า Sum>=n แล้ว
-
res[k] :=อักขระจากโค้ด ASCII (i + ASCII ของ ('a'))
-
n :=n - ผลรวม - temp_sum
-
k :=k + 1
-
ออกจากวง
-
-
ถ้า Sum
-
เหตุการณ์[i] :=เหตุการณ์[i] + 1
-
-
-
-
ผม :=MAX_CHAR-1
-
ในขณะที่ k
=0 ทำ -
หากการเกิดขึ้น[i] ไม่เป็นศูนย์ ดังนั้น
-
res[k] :=อักขระจากโค้ด ASCII (i + ASCII ของ ('a'))
-
เหตุการณ์[i] :=เหตุการณ์[i] - 1
-
ผม :=ผม + 1
-
k :=k + 1
-
-
ผม :=ผม - 1
-
-
return สร้างสตริงจาก res จากดัชนี 0 ถึง (k - 1)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
