我的教授给了我们以下关于寻找一组数字排列的递归算法的解释:
当他有 (T(m+1), n-1)) 时,它从何而来?为什么是m+1和n-1?我真的很困惑这是从哪里来的。
正如他所说,m
表示 的当前大小P
和n
的大小S
,在每个递归调用中,您从中删除一个数字S
并将其添加到P
,因此您当前排列的大小增加了 1 ( m+1
) 和要添加的可用数字的数量对排列减 1 ( n-1
)
n
请注意,当您对 中的每个数字执行此操作时,它会乘以S
。
注意那部分说:
设
m
为 的长度P
和n
为 的大小S
然后在printperm(P, S)
,你打电话printperm((P,i), S-{i})
。
因此,在递归时,我们将向 中添加一个元素P
,并从 中删除元素S
。
因此m
将增加一并n
减少一,因此我们得到T(m+1, n-1)
我希望这会有所帮助。