list - 在这种情况下如何使用 python 递归？

Question

“编写一个名为 anagram(s) 的递归函数，它返回字符串 s 的所有可能字谜的列表。” 我可以就如何解决这个问题获得一些指导吗？我是递归新手，不明白如何为这种情况制作一个更简单的基本案例。或者我的一般算法是什么。

Answer 1

我在上面的评论中链接了一个重复的问题，其中包含了这个问题的实现，但由于这显然是一个类似于家庭作业的任务，我鼓励你将它作为最后的手段。

您的最终目标是列出给定字符串中所有可能的字母组合。

在寻找递归方法时，您需要考虑“我如何才能将这项任务分解为一遍又一遍地做同样的事情，以对抗越来越简单的输入版本。”

因此，与其尝试对整个字符串 ABCD 进行字谜，不如从对第一个字母进行字谜开始：您将获得一组以“A”开头的结果（并在其后包含“BCD”的所有组合），一个以“B”开头（后面是“ACD”的所有组合），以此类推 C 和 D。

这就是递归的第一层；一个接一个地取出每个字母作为第一个字符，然后递归字符串的其余部分。

下一层的第一个实例只需要处理三个字符串“BCD”——你知道所有这些都以“A”开头，你需要递归“B”、“C”和“D”作为第二个字母，其余字母留待洗牌。

更深一层，您从（例如）“AB”开始，并且需要针对“CD”的可能排序进行递归。

递归的底层将是只剩下一个字母，所以没有任何东西可以洗牌；此时，您可以将其附加到前面的字符并返回要添加到您的字谜列表的结果。

您的递归函数将采用两个参数：第一个是“我已经洗牌的字母”，第二个是“我还没有洗牌的字母”。

Answer 2

组合学

我们可以permutations(t)使用归纳推理来写作——

1. 如果输入t为空，则产生空结果
2. (inductive)至少有一个t元素。对于所有子问题，对于所有旋转通过的第一个元素，yieldpt[1:]rt[0]pr

def permutations(t):
  if not t:
    yield ()                          #1
  else:
    for p in permutations(t[1:]):     #2
      for r in rotations(p, t[0]):
        yield r

我们的rotations((a,b,c), X)意思是X将“旋转”通过每个位置(a, b, c)-

(X, a, b, c)
(a, X, b, c)
(a, b, X, c)
(a, b, c, X)

其中rotations(t,e)定义为——

1. 如果输入t为空，则产生空旋转，(e)
2. (inductive)至少有一个t元素。yield并且对于所有子问题，将第一个元素添加到并 yield(e, *t)rt[1:]t[0]r

def rotations(t, e):
  if not t:
    yield (e)                       # 1
  else:
    yield (e, *t)                   # 2
    for r in rotations(t[1:], e):
      yield (t[0], *r)

for p in permutations("same"):
  print(p)

('s', 'a', 'm', 'e')
('a', 's', 'm', 'e')
('a', 'm', 's', 'e')
('a', 'm', 'e', 's')
('s', 'm', 'a', 'e')
('m', 's', 'a', 'e')
('m', 'a', 's', 'e')
('m', 'a', 'e', 's')
('s', 'm', 'e', 'a')
('m', 's', 'e', 'a')
('m', 'e', 's', 'a')
('m', 'e', 'a', 's')
('s', 'a', 'e', 'm')
('a', 's', 'e', 'm')
('a', 'e', 's', 'm')
('a', 'e', 'm', 's')
('s', 'e', 'a', 'm')
('e', 's', 'a', 'm')
('e', 'a', 's', 'm')
('e', 'a', 'm', 's')
('s', 'e', 'm', 'a')
('e', 's', 'm', 'a')
('e', 'm', 's', 'a')
('e', 'm', 'a', 's')

字谜

现在anagrams可以join对产生的排列进行简单的处理 -

def anagrams(s):
  for p in permutations(s):
    yield "".join(p)

for a in anagrams("same"):
  print(a)

same
asme
amse
ames
smae
msae
mase
maes
smea
msea
mesa
meas
saem
asem
aesm
aems
seam
esam
easm
eams
sema
esma
emsa
emas

有效词

如果您只想找到有效的单词，您需要在语句dictionary之前添加一个条件-yield

def anagrams(s, dictionary):
  for p in permutations(s):
    word = "".join(p)
    if word in dictionary:
      yield word

mydict = {"valid", "words", "go", "here", ..., }

for a in anagrams("same"):
  print(a)

same
maes
mesa
seam