理解递归组合代码的问题

选择 | 换行 | 行号
  1. def wordFunc(myDict, currentWord, n):
  2.     if n==0: #Base case
  3.         print(currentWord)
  4.     else: 
  5.         for char in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ":
  6.             if myDict[char] <= 0 :
  7.                 continue
  8.             elif myDict[char] > 0:
  9.                 #Decrease current dictionary's character value by 1 then call function
  10.                 myDict[char] -=1
  11.                 wordFunc(myDict,currentWord+char,n-1)
  12.                 #Increase current dictionary's character value by 1
  13.                 myDict[char] +=1
  14.     return
  15.  
  16.  
  17. k = input() #Get a string from user input
  18.  
  19. myDict = {} #Create dictionary calle dmyDict
  20.  
  21. for char in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ":
  22.     myDict[char] = 0
  23. #Set each letter to a value of 0 for the dictionary
  24. for char in k:
  25.     myDict[char] += 1
  26. #Increase each letter value by 1 everytime it occurs in the input    
  27. wordFunc(myDict,'',len(k))
  28. #Pass in dictionary, blank string, and length of input's string

该代码已经有效,但我不是写它的人。
基本上,代码将一个单词作为输入,它打印出该单词的所有组合。
由于我试图自己学习递归,因此我只是尝试了解此代码数小时,但是我只是无法完全理解正在发生的事情。
如果有人可以向我解释我缺少的东西,我会非常感谢。
我的基本理解是:
如果输入为" ABC",则:
传递包含" ABC"值的字典(每个词的值为1),CurrentWord为''和n = 3
由于a是迭代并选择的for循环的第一个字母:
将A的字典值降低1,以使其为0且无法选择
然后将" +'a"与等于'a',通过n = 2和字典:'a'= 0,'b'= 1,'c'= 1
下次通过,n!= 0,请返回循环。
B是下一个字母:
将B的字典值降低1,使其0
然后将" a' +" b'结合到等于" ab",通过n = 1和字典:'a'= 0,'b'= 0,'c'= 1
下次通过,n!= 0,请返回循环。
C是下一个字母:
将C的字典值降低1,使其0
然后将" ab' +" c'与" abc"相等,然后以n = 0和字典:'a'= 0,'b'= 0,'c'= c
下次通过,n == 0,因此打印单词'abc'。
此后发生的事情是使我感到困惑的部分。
因此,CurrentWord在某种程度上保持在" A",然后随着mydict ['c'] += 1最终传递,我们得到了curentword +c ='a'a' +'c'='ac'
然后,当mydict ['b'] + = 1传递时,我们得到'ac' +'b'='acb'
但是,一旦您最初达到" ABC",CurrentWord如何保持" A"?
我搜索过的这张照片似乎几乎完美地总结了它,但是我仍然不确定它是如何工作的。
我无法缠绕它,对我来说似乎是神奇的。感谢任何有慷慨/耐心向我解释的人!

附件图像

File Type: jpg

E.JPG

(17.9 kb,139次观点)

# 回答1


听起来您相信当前单词每次调用函数时都会引用相同的对象。事实并非如此。在您的示例中,最低函数,其中一个函数n = 0,它将当前单词视为ABC。但是,一旦您退出该功能并返回到更高级别的函数,那个版本的当前单词(等于ABC)不再存在,较高的函数只能看到其当前单词的版本等于AB。
# 回答2


好的,谢谢,我想我要到达某个地方,但是在功能退出并制作字符串ABC之后到底会发生什么?
起初,我想到功能退出后:
它从上次递归呼叫中回到了AB的暂停状态,C增加到1。
然后,它将回到带有A的第二个最后一次递归调用,而B则没有可用,因为此递归调用后它被递增。但是C现在为1,因为增量最终G OT计数,因此添加了交流。 然后使用AC,它再次通过该函数并选择B,因为B的增量最终生效。 因此,第二个排列是ACB 但是后来我查看了这些值,看来C和B选择AC而不是AB时都是1,因此我仍然并不真正理解为什么它再次返回ACB而不是ABC。 有提示吗? 谢谢!
# 回答3

您快到了。 他们都是一个。 但是在上一次迭代中,它已经检查了B,因此不会再次检查它,因此它可以继续检查c。 因此,它以a = 0,b = 1,c = 0和新单词='ac'而递归。 在该函数的新实例中,它再次从a进行检查并找到b。 给你ACB。 但是,当它返回先前的呼叫时,它不会从a开始重新开始检查,它将继续从任何字母中删除。
# 回答4

我的想法被吹了。 谢谢您〜先生〜我想我现在明白了:)

标签: python

添加新评论