Heap算法递归实现无法生成全部排列的问题排查求助

核心问题 #

你代码中声明为类全局成员的i、temp、str是导致排列缺失的根本原因：

• 递归调用过程中所有层级的函数共用同一个全局循环变量i，深层递归修改i的值后，返回上层递归时循环计数会被打乱，导致本该执行的循环迭代直接跳过，少生成对应排列。
• 全局临时变量temp、字符串拼接变量str也存在被多层递归修改的风险，会引发意料之外的结果。

修复方案 #

将所有递归过程中用到的临时变量改为函数内的局部变量，避免跨层级串扰，修复后代码如下：

int[] a;
private void button1_Click(object sender, EventArgs e)
{
    int k = int.Parse(textBox1.Text);
    a = new int[k];
    for (int i = 1; i <= k; i++)
        a[i - 1] = i;
    Generate(a, k);
}
private void Generate(int[] a, int k)
{
    if (k == 1)
    {
        string str = "";
        foreach (int digit in a)
            str += digit.ToString();
        listBox1.Items.Add(str);
        return;
    }
    Generate(a, k - 1);
    for (int 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)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

内容的提问来源于stack exchange，提问作者aldin