1

https://www.ksp.sk/ulohy/zadania/1238/问题链接（斯洛伐克语）

最简单的英文翻译：第一个，命名符号列表，变量是未定义数量的“<”和“>”符号的输入。第二个，命名为 n，是符号列表 + 1 的长度，因为它是这些符号之间的数字数量（例如 2>1<3，符号列表有 2 个符号，n 是 3，数字是范围的列表1-n+1 独占）。我应该为符号打印出正确的数字顺序（例如 4 3 2 1 用于输入 >>>。）
我的代码有效，但根据网站的说法很慢。注释掉的是我基于列表理解的第一个版本。

#combinations(ofwhat,howmanychars)

from itertools import permutations
signlist = [l for z in input() for l in z]
n = len(signlist)+1
ListOfCorrect = [i for i in permutations(range(1,n+1),n) if eval(("{}".join(str(y) for y in i)).format(*signlist))]
print(*ListOfCorrect[0],sep = " ")

#for i in permutations(range(1,n+1),n):
#    forstring1 = ("{}".join(str(y) for y in i)).format(*signlist)
#    if eval(forstring1):
#        print(" ".join(str(y) for y in i))
#        break

#x = list(permutations(range(1,n+1),n))
4

1 回答 1

0

我怀疑你最可控的减速源是建立那个庞大的列表。相反，请单独进行排列。按顺序处理每个表达式（当N很大时应该可以节省时间）；或者，生成所有表达式的列表并使用all归约来命中它们。

对于大型列表来说，也许更好的是获取数字列表 1-n 和运算符列表。在每个级别，将列表拆分为该运营商的合法和非法未使用号码。在合法列表的每个元素上重复出现。

例如，让我们假设你被调用了 [2, 3, 4, 7, 8] 和当前字符串“5<>><>”。您现在只需要接受5 < x的数字x。您获取列表的左侧部分并在 2、3 和 4 中的每一个上重复出现。第一个看起来像：

place_nums( [3, 4, 7, 8], "2>><>" )

这将失败；下一个是

place_nums( [2, 4, 7, 8], "3>><>" )

看看它是如何工作的？平均而言，您将在每个级别重复一半的元素，并在您必须生成所有排列之前修剪死胡同。

这足以让您继续使用递归算法吗？

于 2016-11-29T22:39:25.227 回答