Heap's algorithm

permutations.cpp

/*
Heap's algorithm
https://en.wikipedia.org/wiki/Heap%27s_algorithm

Quentin Deschamps, 2020
*/
#include <iostream>
using namespace std;

void print(int array[], int size)
{
    for (int i(0); i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void heap(int a[], int size, int k)
{
    if (k == 1)
        print(a, size);
    else {
        heap(a, size, k - 1);
        for (int i(0); i < k - 1; i++) {
            if (k % 2 == 0)
                swap(a[i], a[k - 1]);
            else
                swap(a[0], a[k - 1]);
            heap(a, size, k - 1);
        }
    }
}

void print_permutations(int a[], int size)
{
    heap(a, size, size);
}

int main()
{
    int a[] = {1, 2, 3, 4};
    int size = sizeof(a) / sizeof(a[0]);
    print_permutations(a, size);
    return 0;
}