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

Question

“编写一个名为 anagram(s) 的递归函数，returns 列出字符串 s 的所有可能的变位词。”我可以得到一些关于如何解决这个问题的指导吗？我是递归的新手，不了解如何为这种情况制作更简单的基本案例。或者我的通用算法是什么。

Answer 1

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

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

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

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

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

下一层的第一个实例只需要处理三个字符的字符串“BCD”——你知道这些都是以“A”开头的，你需要递归“B”， “C”，“D”为第二个字母，其余字母打乱。

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

递归的底层是只剩下一个字母，所以没有什么可以洗牌的；届时，您只需将其附加到前面的字符，然后 return 将结果添加到您的字谜列表中。

你的递归函数有两个参数：第一个是“我已经打乱的字母”，第二个是“我还没有打乱的字母”。

Answer 2

组合学

我们可以用 inductive reasoning -

来写 permutations(t)

如果输入 t 为空，则产生空结果
（归纳）t 有 至少一个 元素。对于子问题 t[1:] 的所有 p，对于第一个元素 t[0] 旋转通过 p 的所有 r，产生 r

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) 定义为 -

如果输入t为空，yield空旋转，(e)
（归纳）t 有 至少一个 元素。 yield (e, *t) 并且对于子问题 t[1:] 的所有 r，将第一个元素 t[0] 添加到 r 和 yield

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

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

How do I use python recursion in this scenario?

list

recursion

combinatorics

anagram

permute