Most efficient way to select pairs of unique numbers out of many pairs

user_492352 0
Viewed 87

Problem

I have a list of integer pairs. I want to select pairs from this list such that the following conditions would be satisfied:

  • None of the numbers should appear in more than one pair.
  • The maximum number of pairs should be selected.

Notice that there might be multiple answers for the same data, but we just want one.

Example

Let's say our list is the following:

(1, 2)
(2, 3)
(2, 4)
(1, 5)
(10, 11)

The simplest algorithm that guarantees the satisfaction of the first condition only, would be just selecting the first pairs with non-duplicate numbers:

(1, 2)
(10, 11)

However, the valid algorithm that satisfies both, should return the following:

(2, 3) or (2, 4)
(1, 5)
(10, 11)
algorithm
1 Answers

As already mentioned by @kaya3, your problem is called Maximum cardinality matching, and you can read more about this here.

Some people suggested using or-tools for this, and so I wanted to show how it could be done (my solution is probably not the most efficient though).

Preparation

Add a sat solver and prepare initial data:

from ortools.sat.python import cp_model

pairs = [[1, 2],
         [2, 3],
         [2, 4],
         [1, 5],
         [10, 11]]

solver = cp_model.CpSolver()
model = cp_model.CpModel()

Define edges

First, you define an array of boolean variables:

edges = {}
for id1 in range(len(pairs)):
    edges[id1] = model.NewBoolVar('edges[%i]' % id1)

edges[i] is 1 if your pair is included in the final solution, and 0 otherwise.

Pair values are different from the other

For each pair of numbers from the original list, values must be different from values in the other pairs to be included in the final solution.

for i in range(len(pairs)):
    e1 = edges[i]
    pair1_0 = model.NewConstant(pairs[i][0])
    pair1_1 = model.NewConstant(pairs[i][1])
    for j in range(i + 1, len(pairs)):
        e2 = edges[j]
        pair2_0 = model.NewConstant(pairs[j][0])
        pair2_1 = model.NewConstant(pairs[j][1])

        model.Add(pair1_0 != pair2_0).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_1 != pair2_0).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_0 != pair2_1).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_1 != pair2_1).OnlyEnforceIf(e1).OnlyEnforceIf(e2)

Basically, what we do above, is enforce uniqueness of numbers for any pair of pairs (sorry for tautology).

Maximise number of pairs in solution

That's the easiest part. Just enforce that the number of included pairs is maximum:

model.Maximize(sum(edges[id] for id in range(len(edges))))

Show solution

status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print ('Printing solutions below...')
    for i in range(len(pairs)):
        if solver.Value(edges[i]):
            print (pairs[i])

Output

Printing solutions below...

[2, 4]

[1, 5]

[10, 11]

Full Code

from ortools.sat.python import cp_model

pairs = [[1, 2],
         [2, 3],
         [2, 4],
         [1, 5],
         [10, 11]]

solver = cp_model.CpSolver()
model = cp_model.CpModel()

edges = {}
for id1 in range(len(pairs)):
    edges[id1] = model.NewBoolVar('edges[%i]' % id1)

for i in range(len(pairs)):
    e1 = edges[i]
    pair1_0 = model.NewConstant(pairs[i][0])
    pair1_1 = model.NewConstant(pairs[i][1])
    for j in range(i + 1, len(pairs)):
        e2 = edges[j]
        pair2_0 = model.NewConstant(pairs[j][0])
        pair2_1 = model.NewConstant(pairs[j][1])

        model.Add(pair1_0 != pair2_0).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_1 != pair2_0).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_0 != pair2_1).OnlyEnforceIf(e1).OnlyEnforceIf(e2)
        model.Add(pair1_1 != pair2_1).OnlyEnforceIf(e1).OnlyEnforceIf(e2)

model.Maximize(sum(edges[id] for id in range(len(edges))))

status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    print ('Printing solutions below...')
    for i in range(len(pairs)):
        if solver.Value(edges[i]):
            print (pairs[i])
user_10553950
Related