CODEWITHSUNDEEP
carraysalgorithm
abacles
abacles

Reputation: 859

Arranging array into all possible pairs

I am working on a problem (in C) that requires me to list all possible connections between an even number of points, so that every point is connected to only one other point. For example, say I have points 1, 2, 3, and 4:

The order of the points doesn't matter (1 - 2 is same as 2 - 1), and the order of connections doesn't too (1 - 2, 3 - 4 same as 3 - 4, 1 - 2).

I am currently trying to simply order the array such as {1, 2, 3, 4} into all possible orderings and check to see if it is already generated. However this can be very expensive and also the ordering of the points and pairs needs to be disregarded.

What would be a better way to arrange an array into all possible pairs? A basic outline of an algorithm would be appreciated!

Edit: in the example above with {1, 2, 3, 4}, if pairings are represented as two adjacent elements in the array, all possible outcomes would be:

I would need the entire arranged array to perform calculations based on all the connections.

Upvotes: 1

Views: 77

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

This can be accomplished by nondeterministically pairing the rightmost unpaired element and recursing. In C:

void enum_matchings(int n, int a[static n]) {
    if (n < 2) {
        // do something with the matching
        return;
    }
    for (int i = 0; i < n-1; i++) {
        int t = a[i];
        a[i] = a[n-2];
        a[n-2] = t;
        enum_matchings(n-2, a);
        a[n-2] = a[i];
        a[i] = t;
    }
}

Upvotes: 1

Related Questions