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 between the element of A and its pair element of B less than 5 the cost is 2, if the difference is greater than or equal to 10 then the cost is 1 and if the difference is in between 5 and 10(inclusive on 5) then the cost is 0. I need to write a program to find the score of the optimal matching. That is, the minimization of total sum of all n-length possible pair permutations of elements of A with B.

CodePudding user response：

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;
}

CodePudding user response：

You are trying to find one individual pair at each iteration, but you want to minimize the cost over all permutations.

You need to figure out how to generate all permutations of a vector and use code like this:

for permuted_A in all_permutations_of_A
    for permuted_B in all_permutations_of_B
        cost = cost(permuted_A, permuted_B)
        if cost < min_cost
            min_cost = cost
            min_permuted_A = permuted_A
            min_permuted_B = permuted_B

Once you figure out how to enumerate the permutations, the rest will be trivial.