Matching algorithm

Question

I have a list of pencils and a list of erasers. The goal it to check whether or not all the erasers can be put on pencils. An eraser may fit on multiple different pencils. Pencils can have at most 1 eraser.

If I just loop through all the erasers and put them on pencils, I end up with erasers that fit no unoccupied pencils even though there is a solution that has all the erasers on pencils.

What algorithm could I use to figure out a combination that fits all the erasers on pencils?

public class Eraser(){
    public boolean matches(Pencil p){
    //unimportant
    }
}

public class Pencil(){
}

My attempt

public boolean doMatch(List<Eraser> erasers, List<Pencil> pencils){
for (Eraser e : erasers) {
        boolean found = false;
        Iterator it = pencils.iterator();
        while (it.hasNext()) {
            Pencil p = (Pencil) it.next();
            if (e.matches(p)) {
                found = true;
                it.remove();
                break;
            }
        }
        if (!found) {
            return false;
        }
}
return true;
}

Answer 1

You can formulate the problem as Constraint satisfaction problem

The variables would be e.g.

X_i=eraser put on pencil i

the domains

D_i=erasers fitting on pencil i

and the constraints are

X_i != X_j for i!=j

The problem can then be solved with a backtracking algorithm for CSPs. There are many ways to improve the backtracking search with heuristics, for example the "Minimum remaining values" heuristic. A good book is e.g. Russell, Norvig: Artificial Intelligence

Answer 2

Here is a simple solution. I doubt it scales at all well. It could probably be made more efficient by starting with the erasers that fit the fewest pencils.

I have not bothered with an Eraser class. Here there is one Eraser for each index in the matches list.

private static final class Pencil {
    private final int id;
    private Pencil(int id) { this.id = id; }
    @Override
    public String toString() { return "p" + id; }
}

public static void main(String[] args) {
    Pencil p1 = new Pencil(1);
    Pencil p2 = new Pencil(2);
    Pencil p3 = new Pencil(3);
    Pencil p4 = new Pencil(4);
    Pencil p5 = new Pencil(5);
    List<Set<Pencil>> matches = new ArrayList<>();
    matches.add(new HashSet<>(Arrays.asList(p1, p2, p5)));     // First eraser only fits these 3 pencils.
    matches.add(new HashSet<>(Arrays.asList(p3, p4)));         // Second eraser only fits these 2 pencils.
    matches.add(new HashSet<>(Arrays.asList(p3, p5)));         // etc
    matches.add(new HashSet<>(Arrays.asList(p1, p2, p4)));
    matches.add(new HashSet<>(Arrays.asList(p1, p5)));
    System.out.println(allocate(matches));                     // prints [p2, p4, p3, p1, p5]
}

// Returns null if no solution can be found.
private static List<Pencil> allocate(List<Set<Pencil>> matches) {
    return allocate(matches, new ArrayList<>());
}

private static List<Pencil> allocate(List<Set<Pencil>> matches, List<Pencil> solution) {
    int size = solution.size();
    if (matches.size() == size)
        return solution;
    for (Pencil pencil : matches.get(size)) {
        if (solution.contains(pencil))
            continue;
        List<Pencil> copy = new ArrayList<>(solution);
        copy.add(pencil);
        List<Pencil> result = allocate(matches, copy);
        if (result != null)
            return result;
    }
    return null;
}