我正在学习回溯和递归,并且我陷入了打印字符串所有排列的算法。我用以下方法解决了它贝尔算法 http://programminggeeks.com/bell-algorithm-for-permutation/用于排列,但我无法理解递归方法。我在网上搜索了一下,发现了这段代码:
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
}
}
我无法理解这个算法基本上是如何工作的?我什至尝试过干跑!
回溯是如何应用的?
它比贝尔算法计算排列更高效吗?
该算法基本上遵循以下逻辑:
字符串 X 的所有排列与 X 中每个可能字符的所有排列加上字符串 X 中不包含该字母的所有排列相同。
也就是说,“abcd”的所有排列都是
- “a”与“bcd”的所有排列连接
- “b”与“acd”的所有排列连接
- “c”与“bad”的所有排列连接
- “d”与“bca”的所有排列连接
该算法特别不是对子字符串执行递归,而是对输入字符串执行递归,不使用额外的内存来分配子字符串。 “回溯”撤消对字符串的更改,使其保持原始状态。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)