c++algorithmpermutationvariable-assignmentheaps-algorithm

How can I generate all permutations of length n from a set of k elements?


For example I have this set k=5 of elements [1,2,3,4,5] and I want all permutations of length n=2.

1,2
1,3
1,4
1,5
2,1
etc etc. 

Thing is I can't use STL, external math libraries etc.

What I tried is generating all permutations of all the elements using Heap's algorithm, and then all the permutations of n elements where contained in the first n numbers of all k-permutations and I could just truncate and delete duplicates, but then the complexity is way too high(n!)

I know the problem has a good solution as I've seen this being done with extra modules/libraries in questions about permutating strings.

Extra info: I only need this to brute force an unbalanced assignment problem, and Hungarian algorithm seems way too long when I'm allowed to "brute-force" the problem. My approach didn't come close to the allowed execution time because when I have an array of for example size 8x3, my algorithm needs 8! comparisons when it definitely could be optimized to a much smaller number.


Solution

  • I think you can do it in two steps, first, generate combination of k elements out of a set of n, then print permutation of each combination. I tested this code and works fine:

    #include <iostream>
    using namespace std;
    
    void printArr(int a[], int n, bool newline = true) {
        for (int i=0; i<n; i++) {
            if (i > 0) cout << ",";
            cout << a[i];
        }
        if (newline) cout << endl;
    }
    
    // Generating permutation using Heap Algorithm
    void heapPermutation(int a[], int n, int size) {
        // if size becomes 1 then prints the obtained permutation
        if (size == 1) {
            printArr(a, n);
            return;
        }
    
        for (int i=0; i<size; i++) {
            heapPermutation(a, n, size-1);
            // if size is odd, swap first and last element, otherwise swap ith and last element
            swap(a[size%2 == 1 ? 0 : i], a[size-1]);
        }
    }
    
    // Generating permutation using Heap Algorithm
    void heapKPermutation(int a[], int n, int k, int size) {
        // if size becomes 1 then prints the obtained permutation
        if (size == n - k + 1) {
            printArr(a + n - k, k);
            return;
        }
    
        for (int i=0; i<size; i++) {
            heapKPermutation(a, n, k, size-1);
            // if size is odd, swap first and last element, otherwise swap ith and last element
            swap(a[size%2 == 1 ? 0 : i], a[size-1]);
        }
    }
    
    void doKCombination(int a[], int n, int p[], int k, int size, int start) {
        int picked[size + 1];
        for (int i = 0; i < size; ++i) picked[i] = p[i];
        if (size == k) {
            // We got a valid combination, use the heap permutation algorithm to generate all permutations out of it.
            heapPermutation(p, k, k);
        } else {
            if (start < n) {
                doKCombination(a, n, picked, k, size, start + 1);
                picked[size] = a[start];
                doKCombination(a, n, picked, k, size + 1, start + 1);
            }
        }
    }
    
    // Generate combination of k elements out of a set of n
    void kCombination(int a[], int n, int k) {
        doKCombination(a, n, nullptr, k, 0, 0);
    }
    
    int main()
    {
        int a[] = {1, 2, 3, 4, 5};
        cout << "n=1, k=1, a=";
        printArr(a, 1);
        kCombination(a, 1, 1);
    
        cout << "n=2, k=1, a=";
        printArr(a, 2);
        kCombination(a, 2, 1);
    
        cout << "n=3, k=2, a=";
        printArr(a, 3);
        kCombination(a, 3, 2);
    
        cout << "n=5, k=2, a=";
        printArr(a, 5);
        kCombination(a, 5, 2);
        return 0;
    }
    

    The result is:

    n=1, k=1, a=1
    1
    n=2, k=1, a=1,2
    2
    1
    n=3, k=2, a=1,2,3
    2,3
    3,2
    1,3
    3,1
    1,2
    2,1
    n=5, k=2, a=1,2,3,4,5
    4,5
    5,4
    3,5
    5,3
    3,4
    4,3
    2,5
    5,2
    2,4
    4,2
    2,3
    3,2
    1,5
    5,1
    1,4
    4,1
    1,3
    3,1
    1,2
    2,1