how to count and create all possible combinations within a set of pairs?

[jorge5657]

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.

[jorge5657]

Thanks Yarnabrina!

That's right, you are correct in your comment on the problem.

And of course, the set of interest may not be unique, so I'm interested in creating a dataframe with all possible sets, or with all sets of maximum possible elements.

Best,

[technocrat]

I'm unclear on the decision rule. Taking the following example, the aim is to exclude pairs like 10 2 and 2 10 at index 3 and 95? And, if so, both or only one, and if so, the first, the last or the which?

set.seed(42)
A <- sample(1:10,10)
set.seed(137)
B <- sample(1:10,10)
obj <- data.frame(A = A, B = B)
AxB <- unique(expand.grid(obj))
AxB
#>      A  B
#> 1    1  2
#> 2    5  2
#> 3   10  2
#> 4    8  2
#> 5    2  2
#> 6    4  2
#> 7    6  2
#> 8    9  2
#> 9    7  2
#> 10   3  2
#> 11   1  8
#> 12   5  8
#> 13  10  8
#> 14   8  8
#> 15   2  8
#> 16   4  8
#> 17   6  8
#> 18   9  8
#> 19   7  8
#> 20   3  8
#> 21   1  5
#> 22   5  5
#> 23  10  5
#> 24   8  5
#> 25   2  5
#> 26   4  5
#> 27   6  5
#> 28   9  5
#> 29   7  5
#> 30   3  5
#> 31   1  7
#> 32   5  7
#> 33  10  7
#> 34   8  7
#> 35   2  7
#> 36   4  7
#> 37   6  7
#> 38   9  7
#> 39   7  7
#> 40   3  7
#> 41   1  6
#> 42   5  6
#> 43  10  6
#> 44   8  6
#> 45   2  6
#> 46   4  6
#> 47   6  6
#> 48   9  6
#> 49   7  6
#> 50   3  6
#> 51   1  3
#> 52   5  3
#> 53  10  3
#> 54   8  3
#> 55   2  3
#> 56   4  3
#> 57   6  3
#> 58   9  3
#> 59   7  3
#> 60   3  3
#> 61   1  1
#> 62   5  1
#> 63  10  1
#> 64   8  1
#> 65   2  1
#> 66   4  1
#> 67   6  1
#> 68   9  1
#> 69   7  1
#> 70   3  1
#> 71   1  9
#> 72   5  9
#> 73  10  9
#> 74   8  9
#> 75   2  9
#> 76   4  9
#> 77   6  9
#> 78   9  9
#> 79   7  9
#> 80   3  9
#> 81   1  4
#> 82   5  4
#> 83  10  4
#> 84   8  4
#> 85   2  4
#> 86   4  4
#> 87   6  4
#> 88   9  4
#> 89   7  4
#> 90   3  4
#> 91   1 10
#> 92   5 10
#> 93  10 10
#> 94   8 10
#> 95   2 10
#> 96   4 10
#> 97   6 10
#> 98   9 10
#> 99   7 10
#> 100  3 10

[jorge5657]

Hi Technocrat!

Thanks for the comment.
The goal is a little different than what you mention. In your example, the sets \{(2,10)\}, \{(10,2) \} and \{(2,10), (10,2)\} satisfy the rule, since its elements (pairs) do not have elements in common with others pais, given the order.

Best,