在Python中按字符串的字母顺序查找第n个排列

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个长度为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]：=阶乘[i-1] * i

  • 大小：=字符串大小

  • 出现：=大小为MAX_CHAR的数组，用0填充

  • 对于介于0到大小范围内的i，执行

    • 事件[（string [i]）的ASCII-（'a'）的ASCII]：=事件[（字符串[i]）的ASCII-（'a'）的ASCII] + 1

  • res：=大小为MAX_CHAR的数组

  • 和：= 0，k：= 0

  • 虽然Sum与n不同，但是

    • 如果出现[i]与0相同，则

    • 出现[i]：=出现[i]-1

    • temp_sum：=阶乘[大小-1-k]

    • 对于范围0到MAX_CHAR的j，执行

    • 总和：=总和+ temp_sum

    • 如果Sum> = n，则

    • 如果Sum <n，则

    • 进行下一次迭代

    • temp_sum：= temp_sum / factorials [occurrence [j]]（整数除法）

    • res [k]：=来自ASCII码的字符（i +（'a'）的ASCII）

    • n：= n-总和-temp_sum

    • k：= k + 1

    • 从循环中出来

    • 发生[i]：=发生[i] +1

    • 总和：= 0

    • 对于0到MAX_CHAR范围内的i，执行

    • 我：= MAX_CHAR-1

    • 当k <大小且i> = 0时，

      • res [k]：=来自ASCII码的字符（i +（'a'）的ASCII）

      • 出现[i]：=出现[i]-1

      • 我：=我+ 1

      • k：= k + 1

      • 如果出现[i]不为零，则

      • 我：=我-1

    • 将字符串从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

    以上是 在Python中按字符串的字母顺序查找第n个排列 的全部内容， 来源链接： utcz.com/z/321938.html

    回到顶部