c# - 堆算法的问题:并非所有排列都生成
问题描述
我想使用 Heap 算法的递归版本来获得从 1 到 k 的自然数序列的所有排列,但遇到了一些困难。
对于 k = 3,程序输出 123、213、312、132,但由于某种原因,它没有考虑 231 和 321。更具体地说,根据执行 JavaScript 版本算法的视频(https://www.youtube.com/watch?v=xghJNlMibX4),通过第五次排列 k 应该等于 3(在循环中更改)。我不明白为什么在我的情况下它达到 1,并且循环停止执行。
int i, n, temp;
int[] a;
string str = "";
private void button1_Click(object sender, EventArgs e)
{
k = int.Parse(textBox1.Text);
a = new int[k];
for (i = 1; i <= k; i++)
a[i - 1] = i;
Generate(a, k);
}
private void Generate(int[] a, int k)
{
if (k == 1)
{
foreach (int digit in a)
str += digit.ToString();
listBox1.Items.Add(str);
str = "";
return;
}
Generate(a, k - 1);
for (i = 0; i < k - 1; i++)
{
if (k % 2 == 1) Swap(a, 0, k - 1);
else Swap(a, i, k - 1);
Generate(a, k - 1);
}
}
public void Swap(int[] a, int i, int j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
我专注于 Wiki 上的算法变体:https ://en.wikipedia.org/wiki/Heap%27s_algorithm 。有趣的是,我从这里获取的几乎相同的一个:https ://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/工作正常。
看起来我无法从表单的控制台应用程序正确重写它。我可以在不使用递归的情况下尝试该版本,但我仍然想找出在构建递归算法时我的错误是什么。
解决方案
问题是您的循环变量i
是一个全局变量。这意味着当您在循环体内进行递归调用时,该递归将改变该循环变量的值。当递归从它开始的地方返回时,i
将不再具有相同的值,并且循环将过早退出。
所以改变:
for (i = 0; i < k - 1; i++)
至:
for (int i = 0; i < k - 1; i++)
避免全局变量是一种很好的做法,并在您需要它们的地方以尽可能小的范围声明它们。
推荐阅读
- ios - 带有 iOS 应用程序的 Firebase 测试实验室 - 应用程序已安装但未打开
- c++ - 可以删除绑定函数时如何安全使用回调
- c# - Unity:我正在寻找一种方法来比较两个游戏对象在碰撞时的速度
- json - 'chrome_settings_overrides' 的空字典。无法加载清单
- ffmpeg - 如何应用多个裁剪模糊?
- spring-boot - 是否可以使用另一个断路器替代后备方法?
- javascript - 如何将其用作变量而不是字符串?
- react-native - 如何在 React Native 的地图功能中使用复选框?
- java - 在类本身中初始化泛型类型字段
- javascript - 从对象数组返回单个属性