Maximum unique pairings between two lists of repeated items I'm trying to find a general approach to determining how many unique pairs I can form given two lists of items. The elements of each list are different. Within each list, items can be repeated. For example,
list 1     list 2
======     ======
1          A
2          A
2          A
3          A
3          A
3          B
4          B
5          B

Because of repetition, in this case there are only 7 unique pairs possible. ([3,A] must appear more than once). 
If we pair the items in the order they are given, we get 6 unique pairs:
(1,A), (2,A), (3,A), (3,B), (4,B), (5,B) are unique [(2,A) and (3,A) would appear twice]

However, if we pair differently, we can get one more unique pair.
(1,A), (2,A), (2,B), (3,A), (3,B), (4,B), (5,A) are unique [(3,A) would appear twice]

Order doesn't matter (i.e., pair 1,A is the same as A,1).
Is there a general approach to computing the unique possible matchings? Any leads are appreciated.
 A: After looking at various research papers I am fairly comfortable with using the greedy algorithm outlined below, suspecting it always produces a maximum pairing.  In any case there is a quick check to determine when any pairing is a maximum (in linear time in number of vertices).  If this check finds a pairing is not a maximum, then it provides a way to construct a larger pairing.
Greedy algorithm
Take the list with the fewest distinct values (the 2nd list in the example) and pair the highest frequency value there (in this case A) with as many distinct values from the other list as possible.
In this case that produces five distinct pairs:
(1,A), (2,A), (3,A), (4,A), (5,A)

leaving the reduced problem of determining how many distinct matches we can make with B from the second list, and the remaining two distinct values in the first list:
(2,B), (3,B)

One way to think about this is the maximum number of edges in a labelled bipartite graph with (vertex) degree constraints, e.g.
1(1)
2(2)        A(5)
3(3)
4(1)        B(3)
5(1)

where the maximum allowed degrees are shown in parentheses next to the vertex "labels".
In the literature this type of problem is called the "degree constrained subgraph" problem as well as the "maximum cardinality b-matching" problem.  Here $b$ denotes a function on the vertices of a graph $G$, $b: V \to \mathbb{N}$, that gives an upper bound on the degree $\delta(v)$ that vertex would have in a subgraph (subset $M$ of edges of $G$).  Note that if $b\equiv 1$ at all vertices, this notion is simply that of a matching on $G$.
If $G=(X,Y;X\times Y)$ is a complete bipartite graph (as is the case here; any item on one list can be paired with any item on the second list), the problem of determining if the specified degree sequences $\delta(v) = b(v)$ can be attained in a subgraph of $G$ is called the bipartite realization problem, for which a polynomial time algorithm exists by consequence of the Gale-Ryser theorem.  When it succeeds in attaining all the degree bounds exactly, this is essentially the greedy algorithm above.
Formulation as a maximum network flow
The Ford-Fulkerson approach solves the bipartite realization problem, but also the more general problem posed here, of finding the maximum number of pairings (b-matching).
Given the two sets $X$ and $Y$ of distinct values in lists 1 and 2, respectively, define the complete bipartite graph $X\times Y$ and two additional nodes, source $s$ and sink $t$.  If each edge in the complete bipartite graph $X\times Y$ is given capacity 1, and if edges from $s$ to each vertex in $X$ are given capacity equal to the frequency it appears in the first list (degree constraint) and similarly edges from each vertex in $Y$ to $t$ given capacity equal to the frequency in the second list, then the maximum network flow from source to sink will be equal to the maximum cardinality of a b-matching in $G$.
I realize a picture will be helpful here:

This formulation works when $G$ is any bipartite graph, not necessarily complete.  The contribution of Ford and Fulkerson is to find a more efficient algorithm than merely solving the network flow by linear programming (i.e. maximizing flow out of source = flow into sink, subject to the sums of in/out flows cancelling at all internal nodes).
This more efficient algorithm uses the concept of augmenting paths, a path that alternates between edges of $G$ that are included in a current matching and edges that are not.  A b-matching is a maximum if and only if there is no augmenting path, but if there is an augmenting path, this can be used to increase the size of the b-matching.  The search for an augmenting path can be done in time linear to the number of vertices of $G$.
A fairly recent paper in this area is An $O(n^3)$ time algorithm for the maximum weight b-matching problem on bipartite graphs (Oct. 2014).
For a more historical introduction I recommend Edmonds, Matching, and the Birth of Polyhedral Combinatorics by William R. Pulleyblank, though it quickly moves beyond the treatment of bipartite graphs to matchings in general graphs by Jack Edmonds "blossom algorithm".
