Maximum number of pairings

[Pompey_Dan]

Hi,

First time poster here and desperately in need of some help!

I have a long list of applicants that have been matched using various criteria, however, some of these applicants have multiple matches and I need to determine the maximum number of pairings that could be achieved.

Example:

1st Applicant	Matched Applicant
Applicant A	Applicant B
Applicant A	Applicant C
Applicant B	Applicant A
Applicant B	Applicant C
Applicant C	Applicant A
Applicant C	Applicant B

In the example there are three possible matches (A with B, A with C, and B with C) but the maximum number of pairings is one because Applicant A can only be matched with one of Applicant B or Applicant C, leaving the other (B or C) without a pair.

There are 1186 rows of data in my worksheet, and a total number of 593 potential matches, but I need to determine the maximum number of pairings that could be achieved (which I expect to be far lower than 593)... think of it like a dating agency at work, pairing up potential couples in an attempt to clear it's books (although what I'm trying to do is far more mundane!!)

Any help would be much appreciated, thank you.

 

[StephenCrump]

Welcome to the Forum!

There are 1186 rows of data in my worksheet, and a total number of 593 potential matches ...

Ir will be fewer than that. Suppose you have 6 applicants, and each is happy to partner with the other 5. If you list them as you have done, you'll have 6 x 5=30 lines, but a maximum of 3, not 15, matches.

Can you please let us know in your Account details what version of Excel you're using? If you have the latest version, it may be feasible to do this with formulae - perhaps using a recursive LAMBDA.

But I'd do this in VBA. Is that an option for you?

If so, here's how I'd structure this:

	A	B	C	D	E	F	G	H	I	J	K	L	M
1		B	C	D	E	F
2	A	x	x	x				Pair	Possibilities --->
3	B			x		x		1	AB	AC	AC	AD	AD
4	C				x			2	CE	BD	BF	BF	EF
5	D							3		EF		CE
6	E					x
7	F
8
Sheet1

The table shows that:

- A is a match for B, C and D.
- B is a match for D and F (we don't need to show the A-B match again)
- etc etc

So the code simply needs to loop through the possibilities:
Pair 1: Match A with B, C or D
Pair 2: For each of the three Pair 1 possibilities, make a second match out of the remaining possibilities.
Pair 3: For each of the Pair 1/Pair 2 possibilities, make a third match out of the remaining possibilities.

The resulting list to the right shows there are two ways to make three matches for this group.

In a bigger more complicated example, we'd also need to allow for people not to be matched. So the first pair here would be AB, AC, AD or A-unmatched, because A-unmatched could lead to the greatest number of pairings in a longer example.