Problem with Heap's algorithm: not all permutations are generated-CodePudding

I wanted to use the recursive version of Heap's algorithm in order to get all permutations of a sequence of natural numbers from 1 to k inclusive, but ran into certain difficulties.

For k = 3, the program outputs 123, 213, 312, 132, but for some reason it does not take 231 and 321 into account. More specifically, according to the video with the implementation of the JavaScript version of the algorithm (https://www.youtube.com/watch?v=xghJNlMibX4), by the fifth permutation k should become equal to 3 (changing in the loop). I don't understand why in my case it reaches 1, and the loop stops executing.

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;
}

I focused on a variant of the algorithm found on the Wiki: https://en.wikipedia.org/wiki/Heap's_algorithm. Interestingly, the almost identical one which I took from here: https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/ works correctly.

It looks like I haven't been able to rewrite it correctly from a console application for forms. I can try that version without recursion, but I still want to find out what my mistake was when building a recursive algorithm.

CodePudding user response：

The problem is that your loop variable i is one global variable. This means that when you make a recursive call inside the loop's body, that recursion will alter the value of that loop variable. When the recursion comes back from where it was initiated, i will no longer have the same value, and the loop will exit prematurely.

So change:

    for (i = 0; i < k - 1; i  )

to:

    for (int i = 0; i < k - 1; i  )

It is good practice to avoid global variables, and to declare them with the smallest scope possible, there where you need them.