我真的很难理解递归代码。我复制了一段我想要理解的代码。我已经看到了以图形化的方式描述这一点,但我不明白程序是如何得到结果的。
到目前为止,这是我的理解
最初为
如果条件不满足,则将
,i+1,
这有意义吗?请有人解释一下这段代码是如何产生所有解决方案的。谢谢
def permute(data, i, length):
if i==length:
print(''.join(data) )
else:
for j in range(i,length):
#swap
data[i], data[j] = data[j], data[i]
permute(data, i+1, length)
data[i], data[j] = data[j], data[i]
string = "ABC"
n = len(string)
data = list(string)
permute(data, 0, n)
发布于 2019-04-17 06:49:13
让我们逐行分解代码。我们将从字符串的开头步进到结尾,在每次调用时递增i
。在每次调用中,我们对字符串的其余部分迭代j
。
def permute(data, i, length):
# If "i" is at the end, we're done with one permutation: print the result.
if i==length:
print(''.join(data) )
else:
# for each remaining character (later in the string)
for j in range(i,length):
# Swap that character with the "ith" character
data[i], data[j] = data[j], data[i]
# Keeping data[0:i] fixed,
# generate all permutations of the remainder of the string
permute(data, i+1, length)
# Swap the characters back
data[i], data[j] = data[j], data[i]
现在,添加一些基本的工具来跟踪执行:跟踪例程条目和递归;每次重复时缩进。
indent = ""
def permute(data, i, length):
global indent
print(indent, "ENTER", ''.join(data), i)
indent += " "
if i==length:
print("PERMUATATION:", ''.join(data) )
else:
for j in range(i,length):
print(indent, "SWAP", i, j)
#swap
data[i], data[j] = data[j], data[i]
permute(data, i+1, length)
data[i], data[j] = data[j], data[i]
indent = indent[2:]
string = "ABC"
n = len(string)
data = list(string)
permute(data, 0, n)
输出:
ENTER ABC 0
SWAP 0 0
ENTER ABC 1
SWAP 1 1
ENTER ABC 2
SWAP 2 2
ENTER ABC 3
PERMUATATION: ABC
SWAP 1 2
ENTER ACB 2
SWAP 2 2
ENTER ACB 3
PERMUATATION: ACB
SWAP 0 1
ENTER BAC 1
SWAP 1 1
ENTER BAC 2
SWAP 2 2
ENTER BAC 3
PERMUATATION: BAC
SWAP 1 2
ENTER BCA 2
SWAP 2 2
ENTER BCA 3
PERMUATATION: BCA
SWAP 0 2
ENTER CBA 1
SWAP 1 1
ENTER CBA 2
SWAP 2 2
ENTER CBA 3
PERMUATATION: CBA
SWAP 1 2
ENTER CAB 2
SWAP 2 2
ENTER CAB 3
PERMUATATION: CAB
现在使用此信息跟踪代码。
https://stackoverflow.com/questions/55717523
复制相似问题