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

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.

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,

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


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,

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.

If you have a query related to it or one of the replies, start a new topic and refer back with a link.