Heap's permutation generation algorithm generating duplicate results

Question

I am using Heap's algorithm for generating all the permutations of a list, but for some reason my implementation is not working. Specifically, it produces the correct number of permutations, n!, but it is missing some and fills in the gaps with copies of previous permutations. Here is what it produces with 3 items: (first instance of duplicates marked with f, second instance with s, third with t, marking done by me not code)

0, 1, 2,
1, 0, 2,
2, 1, 0, f
1, 2, 0, f
2, 1, 0, s
1, 2, 0, s

This is what it produces with four items:

0, 1, 2, 3,
1, 0, 2, 3,
2, 1, 0, 3, f
1, 2, 0, 3, f
2, 1, 0, 3, s
1, 2, 0, 3, s
3, 1, 2, 0,
1, 3, 2, 0, f
2, 1, 3, 0,
1, 2, 3, 0, f
0, 1, 3, 2,
1, 0, 3, 2,
1, 3, 2, 0, s
0, 3, 2, 1,
2, 3, 1, 0, f
0, 3, 1, 2, f
3, 2, 1, 0, f
1, 2, 3, 0, s
2, 3, 1, 0, s
0, 3, 1, 2, s
3, 2, 1, 0, s
1, 2, 3, 0, t
2, 3, 1, 0, t
0, 3, 1, 2, t

Here is my code:

vector<vector<int>> permutations;

void GenerateAllPermutations(vector<int> v, int size)
{
    // if size becomes 1 then adds on the obtained permutation
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);

        // if size is odd, swap first and last element
        if (size % 2 == 1)
        {
            iter_swap(v.begin(), v.begin() + v[size - 1]);
        }
        // If size is even, swap ith and last element
        else
        {
            iter_swap(v.begin() + i, v.begin() + v[size - 1]);
        }
    }
}

int main()
{
    vector<int> v = { 0, 1, 2, 3 };
    GenerateAllPermutations(v, v.size());
    // prints all the generated permutations
    for (int i = 0; i < permutations.size(); i++)
    {
        for (int x = 0; x < permutations[i].size(); x++)
        {
            cout << permutations[i][x] << ", ";
        }
        cout << endl;
    }
}

You'll be glad to hear you don't need anyone's help to figure this out, just a tool you already have: your debugger! This is exactly what a debugger is for. It [runs your program, one line at a time, and shows you what's happening](https://stackoverflow.com/questions/25385173/), this is something that's every C++ developer must know how to do. With your debugger's help you'll able to quickly find all problems in this and all future programs you write, without having to ask anyone for help. Have you tried using your debugger, already? If not, why not? What did your debugger show you? — Sam Varshavchik, Aug 09 '23 at 11:20
Agreed, this is a *great* problem for learning to use the debugger. Additionally, maybe take a look at the sequence being output, and the expected result of Heap's Algorithm, and specifically concentrate on the first row where the results don't match the expectation. What's the first swap that's incorrect, and how did it happen? — Sneftel, Aug 09 '23 at 11:23
Also, not to give you too big a hint, but have you tried numbers other than 0,1,2,3? Like, say, 0,10,20,30? — Sneftel, Aug 09 '23 at 11:24
Perhaps the problem might be because "swap the first and last element" does not swap the first and last element? — Sam Varshavchik, Aug 09 '23 at 11:25
Another big hint: if you try it with `vector` , your compiler will tell you something. — molbdnilo, Aug 09 '23 at 11:31
`void GenerateAllPermutations(vector v, int size)` -- Did you realize that the first parameter `v` is passed by-value? It means that `v` inside `GenerateAllPermutations` is a copy, and that copy goes away as soon as that function returns. This means that all of your changes to `v` are gone when you return. Unlike other languages, C++ makes copies of objects when passed this way to functions -- C++ is not C#. — PaulMcKenzie, Aug 09 '23 at 13:06

score 1 · Accepted Answer · answered Aug 09 '23 at 13:19

There are two bugs in your code:

v.begin() + v[size - 1] makes no sense: v[size - 1] is in not an offset, but a data value. This should be v.begin() + size - 1
The recursive version of Heap's algorithm intends to have each recursive manipulate the same array, but vectors are passed by value, and since they are not pointers, the mutation to that vector will just happen for that execution context, not for the caller's vector. See also Are vectors passed to functions by value or by reference in C++ and Passing a vector by reference by the values are not changing in original vector which is passed?

With those corrections it will work:

// pass vector by reference
void GenerateAllPermutations(std::vector<int> &v, int size)
{
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);
        if (size % 2 == 1)
        {
            // Don't pass a data value, but an offset
            iter_swap(v.begin(), v.begin() + size - 1);
        }
        else
        {
            iter_swap(v.begin() + i, v.begin() + size - 1);
        }
    }
}

Although this now works, it performs more swaps than necessary. See Wikipedia's section on Frequent mis-implementations which discusses your version of the algorithm:

This implementation will succeed in producing all permutations but does not minimize movement. As the recursive call-stacks unwind, it results in additional swaps at each level. Half of these will be no-ops of [] and [−1] where ==−1 but when is odd, it results in additional swaps of the ^th with the 0^th element.

Heap's permutation generation algorithm generating duplicate results

1 Answers1