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

Question

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%27s_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.

Have you done step-through debugging on the iteration to see if the actual values match what you expect? — Andrew H
– Andrew H, Commented Oct 1, 2021 at 18:47
Yes, that's why I found that in the end of the loop k = 3. It was extremely hard to compare every step of two codes, so I dropped that eventually and tried to make an assessment of the situation as a whole. — aldin
– aldin, Commented Oct 1, 2021 at 19:42

trincot · Accepted Answer · 2021-10-01 19:48:29Z

2

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.

answered Oct 1, 2021 at 19:48

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Andrew H Over a year ago

I would suggest applying the same treatment to int[] a and int temp as well.

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related