“撰寫一個名為 anagram(s) 的遞回函式，它回傳字串 s 的所有可能的 anagrams 的串列。” 我能得到一些關于如何解決這個問題的指導嗎？我是遞回的新手，不明白如何為這種情況制作一個更簡單的基本案例。或者我的通用演算法是什么。
uj5u.com熱心網友回復：
我在上面的評論中鏈接了一個重復的問題，其中包含對此的實作，但由于這顯然是一項類似于家庭作業的任務，我鼓勵您將其用作最后的手段。
您的最終目標是列出給定字串中字母的所有可能組合。
在尋找遞回方法時，您需要考慮“我如何才能將此任務分解為針對越來越簡單的輸入版本一遍又一遍地做同樣的事情”。
因此，與其嘗試對完整的字串 ABCD 進行變位，不如從對第一個字母進行變位開始：您將獲得一組以“A”開頭的結果（并且后面有“BCD”的所有組合），以“B”開頭（后面是“ACD”的所有組合），對 C 和 D 依此類推。
所以這是你遞回的第一層；一個一個地提取每個字母作為第一個字符，并用字串的其余部分遞回。
下一層的第一個實體只需要處理一個三個字符的字串“BCD”——你知道所有這些都以“A”開頭，你需要遞回“B”、“C”和“D”作為第二個字母，剩下的字母待洗牌。
更深一層，您從（例如）“AB”開始，并且需要針對“CD”的兩種可能順序進行遞回。
遞回的底層將是當只剩下一個字母時，所以沒有什么可以洗牌了；在這一點上，您可以將它附加到前面的字符并回傳要添加到字謎串列中的結果。
您的遞回函式將采用兩個引數：第一個是“我已經洗牌的字母”，第二個是“我尚未洗牌的字母”。
uj5u.com熱心網友回復：
組合學
我們可以permutations(t)用歸納推理來寫——
- 如果輸入
t為空，則產生空結果 - （電感性）
t具有至少一個元件。對于所有p子問題t[1:]，對于所有旋轉通過r的第一個元素，屈服t[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)定義為 -
- 如果輸入
t為空，則產生空旋轉，(e) - （電感性）
t具有至少一個元件。yield(e, *t)并且對于所有r子問題t[1:]，將第一個元素添加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
有效詞
如果您只想找到有效的單詞，則需要 adictionary并在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
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/371664.html