Unable to find the optimal cost of pairing elements of two sets

Question

Given two sets of natural number A and B of size n such that each member of A has to be paired to at at most one member of B. There is also cost associated with each pairing i.e if the absolute difference b\l sum of all n-length possible pair permutations of elements of A with B.

Answer 1

The following (crude and far from being optimized and safe -- I used a global variable: horror!) code does the job:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>


#define SWAP(x, y, T) do { T SWAP = x; x = y; y = SWAP; } while (0)

int factorial(int N) {
    int product = 1;
    for (int j = 1; j <= N; j++)
        product *= j;
    return product;
}

// Prints the array
void printArr(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// Stores the array
void storeArr(int a[], int n, int counter, int** out)
{
    for (int i = 0; i < n; i++) {
        out[counter][i] = a[i];
    }
}

int get_cost(int a, int b) {
    int diff = abs(a - b);
    if (diff >= 5 && diff < 10) {
        return 0;
    }
    else if (diff < 5) {
        return 1;
    }
    else {
        return 2;
    }
}

int cost_perm(int* a, int* b, int n) {
    int cost = 0;
    for (int i = 0; i < n; ++i) {
        cost += get_cost( a[i], b[i] );
    }
    return cost;
}

// Globals are bad but...
int counter;

// Generating permutation using Heap Algorithm
void heapPermutation(int a[], int size, int n, int** out)
{
    // if size becomes 1 then stores the obtained
    // permutation
    if (size == 1) {
        storeArr(a, n, counter++, out);
        return;
    }
 
    for (int i = 0; i < size; i++) {
        heapPermutation(a, size - 1, n, out);
 
        // if size is odd, swap 0th i.e (first) and
        // (size-1)th i.e (last) element
        if (size % 2 == 1)
            SWAP(a[0], a[size - 1], int);
 
        // If size is even, swap ith and
        // (size-1)th i.e (last) element
        else
            SWAP(a[i], a[size - 1], int);
    }
}
 
// Driver code
int main()
{
    int a[] = { 169, 165, 161, 131, 145 };
    int b[] = { 214, 174, 218, 188, 168 };
    int n = sizeof a / sizeof a[0];
    int numperm = factorial(n);

    int** perm_of_a = calloc(numperm, sizeof(int*));
    int** perm_of_b = calloc(numperm, sizeof(int*));

    for (int i = 0; i < numperm; ++i) {
        perm_of_a[i] = calloc(n, sizeof(int));
        perm_of_b[i] = calloc(n, sizeof(int));
    }

    counter = 0;
    heapPermutation(a, n, n, perm_of_a);
    counter = 0;
    heapPermutation(b, n, n, perm_of_b);

    int min_cost = 1000;
    int cost;
    int mina = 0;
    int minb = 0;
    for (int i = 0; i < numperm; ++i) {
        for (int j = 0; j < numperm; ++j) {
            cost = cost_perm(perm_of_a[i], perm_of_b[j], n);
            if (cost < min_cost) {
                min_cost = cost;
                mina = i;
                minb = j;
            }
        }
    }

    printArr( perm_of_a[mina], n );
    printArr( perm_of_b[minb], n );
    printf( "%d\n", min_cost );

    return 0;
}