Simple pair matching algorithm with binary preferences

Question

I'm looking for a pair matching algorithm for a really simple problem:

• People self-assign into categories A or B or both A and B.
• They express preferences: to be matched with people in categories A, B, or either.
• Everyone is paired up (unless an odd number). Score 2 points if both people's preferences have been met, 1 if 1 person's preferences are met, 0 otherwise.

I want to find an algorithm that produces the optimal result possible for any given set of people.

Additional requirement: the chance of a person ending up unpaired must never be reduced by adding an additional category or preference. (It's ok if removing a category or preference harms their chances, however.)

There are algorithms for more complex scenarios like the Stable Marriage Problem, but my situation seems pretty simple - I'm just not sure how to go about it. The total number of people will be in the 20-50 range, so inefficient solutions are fine.

Example:

"1. A -> A,B" means person 1 is in category A and wants to match someone in either A or B.

Let's say we have these people:

1. A -> A,B
2. A -> B
3. A -> B
4. A -> A
5. B -> A
6. B -> A

I think we can see by inspection that an optimum solution is 1+4, 2+5, 3+6.

Cost function

In case the text description above wasn't sufficiently formal, the scoring I mean:

• A->A + A->A, B->B + B->B, A->B + B->A: 2 points
• A->A + B->A, A->B + B->B, A->B + A->A, B->A + B->B: 1 point
• A->A + B->B, A->B + A->B, B->A + B->A: 0 points

Answer 1

Its a kind of inefficient solution but i think it works. First i use a class person which has 3 private attitudes id, category and preference.

public class Person {
private String category;
private String pref;
private int id;

/**
 * The strings a,b will be A for A, B for B and A,B for Both 
 * @param a expressing the category that they want to go
 * @param b expressing the preference
 */
Person(int id,String a,String b){
    this.id=id;
    category=a;
    pref=b;
}

public String getCategory(){
    return category;
}

public String getPref(){
    return pref;
}

public int getId(){
    return id;
}

}

In the main class i take data from a txt file named a.txt and the format of each person has to be A -> B like the one you gave. It runs 3 private methods to get first the matches that give 2 points, then the mathces that give 1 point and then fill the rest.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Pairing {
private ArrayList<Person> queue;
private ArrayList<String> matches;
private int ids;

public Pairing() {
    queue = new ArrayList<>();
    ids = 0;

}

public void addPerson(String category, String preference) {
    queue.add(new Person(ids, category, preference));
    ids++;

}

public ArrayList<String> getMatches() {
    matches = new ArrayList<>();
    System.out.println(ids);
    checkFor2Points();
    checkFor1Point();
    //matchTheRest();
    return matches;
}

/**
 * At the begin matches the persons who has strict preferences and belongs
 * in the first 2 categories, then uses the flexibility that A,B category
 * provides to find the rest matches that will give 2 points.
 */
private void checkFor2Points() {
    Person c, p;
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        System.out.println(p.getCategory() + " " + p.getPref());
        if ((p.getCategory().equals("A") || p.getCategory().equals("B")) && (p.getPref().equals("A") || p.getPref().equals("B"))) {
            for (int i = 0; i < queue.size(); i++) {
                c = queue.get(i);
                if (c.getPref().equals(p.getCategory()) && c.getCategory().equals(p.getPref()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                } else if (c.getCategory().equals("A,B") && c.getPref().equals(p.getCategory()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                }
            }
        }
    }
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        if (p.getPref().equals("A,B")) {
            for (int i = 0; i < queue.size(); i++) {
                c = queue.get(i);
                if (c.getPref().equals(p.getCategory()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                }
            }
        }
    }

}

private void checkFor1Point() {
    Person c, p;
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        for (int i = 0; i < queue.size(); i++) {
            c = queue.get(i);
            if ((p.getCategory().equals(c.getPref()) || p.getPref().equals(c.getCategory())) && p.getId() != c.getId()) {
                matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                queue.remove(c);
                queue.remove(p);
            }
        }
    }

}

private void matchTheRest() {
    for (int i = 0; i < queue.size(); i += 2) {
        matches.add(queue.get(i).getId() + "+" + queue.get(i + 1).getId());
        queue.remove(queue.get(i));
        queue.remove(queue.get(i + 1));
        if (queue.size() == 1) {// that means that the ids is an odd number
            return;
        }
    }
}

/**
 * @param args the command line arguments
 * @throws java.io.FileNotFoundException
 */
public static void main(String[] args) throws FileNotFoundException, IOException {
    String getLineString;
    String toSplit[];
    BufferedReader in = new BufferedReader(new FileReader("a.txt"));
    Pairing pair = new Pairing();
    getLineString = in.readLine();
    while (getLineString != null) {
        toSplit = getLineString.split(" -> ");
        pair.addPerson(toSplit[0], toSplit[1]);
        getLineString = in.readLine();
    }
    ArrayList<String> pairs = pair.getMatches();
    for (int i = 0; i < pairs.size(); i++) {
        System.out.println(pairs.get(i));
    }

}

}