时间戳

首页 > 解决方案 > 递归计算具有最大位移的排列数

python - 递归计算具有最大位移的排列数

问题描述

我创建了一个名为 permutations_dist(s, dist) 的递归函数。

它应该返回一个字符串的排列数，而排列中每 2 个字母之间的距离不超过给定的数字。

几个例子：

permutations_dist("abc", 1) --> 2
permutations_dist("abc", 1000) --> 6
permutations_dist("abcz", 23) --> 4

如何使以下代码更高效？我想使用回溯。

它很快就达到了最大递归深度。例如 - permutations_dist("abcdefghijkm", 3))。

编码：

def permutations_dist(s, dist):
    return len(permutations_dist_helper(s, dist))

def permutations_dist_helper(s, dist):
   if len(s) == 1:
       return [s]

   perm_list = []  # resulting list
   for a in s:
       remaining_elements = [x for x in s if x != a]
       z = permutations_dist_helper(remaining_elements, dist)

       for t in z:
           if abs(ord(a) - ord(t[0])) <= dist:
               perm_list.append([a] + t)

    return perm_list

标签： pythonpython-3.xrecursionpermutation

解决方案

最好使用堆栈来避免超过最大递归深度。下面的代码生成所有两个相邻字符之间的最大距离不超过dist的字符串排列：

def permutations(s, dist):
    result = set()
    stack = [("", s, 0)]

    while stack:
        cur, remaining, cur_distance = stack.pop(0)

        if remaining:
            candidates = set()
            for i in range(0, len(remaining)):
                m = remaining[i]
                diff = abs(ord(m) - ord(cur[-1])) if cur else 0
                new_distance = max(cur_distance, diff)
                if new_distance <= dist:
                    head = cur + m
                    candidates.add((head, remaining[:i] + remaining[i+1:], new_distance))
            for c in candidates:
                stack.append(c)
        else:
            result.add(cur)

    return result

让我们检查计算permutations("abcdefghijk", 3)需要多长时间：

from time import time
start = time()
dist = len(permutations("abcdefghijk", 3))
end = time()
print("Premutations: {}, execution time: {:05f}".format(dist, end - start))

在我的 MacBook 上显示

Premutations: 13592, execution time: 0.663339

推荐阅读