Hi all!

I am trying to implement a code that allows to count and create all possible combinations of a set of pairs, with **the condition that no element is repeated between pairs.**

That is, given two sets:

A=\{1,2,3,...,n_A\}

B=\{1,2,3,...,n_B\}

I know that the set A\times B:=\{(a,b) : a \in A, b \in B\} has n_A*n_B elements. But I'm interested in family of sets:

C \subset A\times B,\: C= \{(a, b) \in A\times B: a \neq a ', \text{ and }, b \neq b \: \: \forall (a, b), (a', b ') \in C\}.

I'm interested in that set C with the maximum number of elements (given A and B ), and how to implement a code to create all the elements of this set.

For example, given A=\{1,2 \}, B=\{1,2\}, I have this code:

*na <- 2*

*nb <- 2*

*a <- rep(1:na, each = nb)*

*b <- rep(1:nb, times = na)*

*df <- data.frame(a,b)*

that return in every row each elements of A\times B. But suppose I take a subset of this set, C \subset A\times B (i.e. a sample of this dataframe), my goal is to find all possible sets of pairs (a, b) \in C , such that between these pairs no elements are repeated.

In the example above, the set A \times B is (in dataframe format, "value" variable is defined next ):

*var1 var2 value*

*1 1 x*

*1 2 y*

*2 1 z*

*2 2 w*

if I take the following sample:

*var1 var2 value*

*1 1 x*

*1 2 y*

*2 1 z*

All sets of interest are:

*var3 (string) var4_1 (num) var4_2(num)*

*"1-1" x 0*

*"1-2" y 0*

*"2-1" z 0*

*"1-2,2-1" y z*

**In particular, I'm interested in building this last dataframe, with the variables "var4", "var4_1", "var4_2", ..., "var4_g", with g = maximum number of pairs in a set C.**

I hope you can guide me in the procedure to build the code.

Best,

Jorge.

P.S: this thinking of analyzing every possible matching in marriage markets.