Tìm hoán vị từ điển thứ n của một chuỗi trong Python

Giả sử chúng ta có một chuỗi có độ dài là m và chuỗi này chỉ chứa các chữ cái viết thường, chúng ta phải tìm hoán vị thứ n của chuỗi theo từ điển.

Vì vậy, nếu đầu vào là string ="pqr", n =3, thì đầu ra sẽ là "qpr" vì tất cả các hoán vị là [pqr, prq, qpr, qrp, rpq, rqp], chúng được sắp xếp theo thứ tự.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MAX_CHAR:=26

• MAX_FACT:=20

• giai thừa:=một mảng có kích thước MAX_FACT

• giai thừa [0]:=1

• đối với tôi trong phạm vi từ 1 đến MAX_FACT, hãy thực hiện

  • factorials [i]:=factorials [i - 1] * i

• size:=kích thước của chuỗi

• xuất hiện:=một mảng có kích thước MAX_CHAR, điền bằng 0

• đối với tôi trong phạm vi từ 0 đến kích thước, hãy làm

  • xuất hiện [ASCII của (string [i]) - ASCII của ('a')]:=xuất hiện [ASCII của (string [i]) - ASCII của ('a')] + 1

• res:=một mảng có kích thước MAX_CHAR

• Tổng:=0, k:=0

• trong khi Sum không giống với n, do

  • Tổng:=0

  • đối với tôi trong phạm vi từ 0 đến MAX_CHAR, hãy thực hiện

    • nếu lần xuất hiện [i] giống 0 thì

      • chuyển sang lần lặp tiếp theo

    • Lần xuất hiện [i]:=Lần xuất hiện [i] - 1

    • temp_sum:=factorials [size - 1 - k]

    • đối với j trong phạm vi 0 đến MAX_CHAR, thực hiện

      • temp_sum:=temp_sum / factorials [Lần xuất hiện [j]] (phép chia số nguyên)

    • Tổng:=Sum + temp_sum

    • nếu Sum> =n, thì

      • res [k]:=ký tự từ mã ASCII (i + ASCII của ('a'))

      • n:=n - Tổng - temp_sum

      • k:=k + 1

      • đi ra từ vòng lặp

    • nếu Sum

      • Lần xuất hiện [i]:=Lần xuất hiện [i] + 1

• i:=MAX_CHAR-1

• while k =0, do

  • nếu lần xuất hiện [i] khác 0, thì

    • res [k]:=ký tự từ mã ASCII (i + ASCII của ('a'))

    • Lần xuất hiện [i]:=Lần xuất hiện [i] - 1

    • i:=i + 1

    • k:=k + 1

  • i:=i - 1

• trả về tạo chuỗi từ res từ chỉ mục 0 đến (k - 1)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"pqr"

Đầu ra

qpr