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

[jorge arenas molina]

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,...,nA}
B={1,2,3,...,nB}

I know that the set A×B:={(a,b):a∈A,b∈B} has nA∗nB elements. But I'm interested in family of sets:
C⊂A×B , C={(a,b)∈A×B:a≠a′, and ,b≠b∀(a,b),(a′,b′)∈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:
scalar na=2
scalar nb=2
set obs `=na*nb'
egen A=seq(), from(1) to(`=na') block(`=nb')
egen B=seq(), from(1) to(`=nb') block(1)
that return in every row each elements of A×B . But suppose I take a subset of this set, C ⊂ A×B (i.e. a sample of this dataframe), my goal is to find all possible sets of pairs (a,b) ∈ C , such that between these pairs no elements are repeated.
In the example above, the set A×B is (in data format, "value" variable is defined next ):
A B value
1 1 x
1 2 y
2 1 z
2 2 w

if I take the following sample:
A B 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 data, 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.

[Andrew Musau]

Do you want the largest subset that can be drawn from the Cartesian product of sets A and B such that no elements in either set is repeated? Consider that there is no guarantee that such a set is unique. If you have

$$A \times B= \{ (a_1, b_1), (a_1, b_2), (a_2, b_1), (a_2, b_2)\}$$

then either

$$C_1 \subset A \times B= \{ (a_1, b_2), (a_2, b_1)\}$$

or

$$C_2 \subset A \times B= \{ (a_1, b_1), (a_2, b_2)\}.$$

satisfy the definition.

[jorge arenas molina]

Hi Andrew!

Thanks for the comment. Of course, this set may not be unique. For this reason, I am interested in creating all possible sets, or all these sets with a maximum number of elements.

I'm trying with the "fillin" command, but I need to identify (and delete) those sets that have elements in common between the pairs, and also those sets that only change the order of their elements.

Best,

[Andrew Musau]

You can install tuples from SSC, then extract all combinations and specify a condition to check repetitions within observations (rows). Let me know if you have difficulties doing this. For my example:

*ssc install tuples
tuples a1b1 a1b2 a2b1 a2b2
macro list

Res.:

_ntuples:       15
_tuple15:       a1b1 a1b2 a2b1 a2b2
_tuple14:       a1b1 a1b2 a2b1
_tuple13:       a1b1 a1b2 a2b2
_tuple12:       a1b1 a2b1 a2b2
_tuple11:       a1b2 a2b1 a2b2
_tuple10:       a1b1 a1b2
_tuple9:        a1b1 a2b1
_tuple8:        a1b1 a2b2
_tuple7:        a1b2 a2b1
_tuple6:        a1b2 a2b2
_tuple5:        a2b1 a2b2
_tuple4:        a1b1
_tuple3:        a1b2
_tuple2:        a2b1
_tuple1:        a2b2

A search will reveal that the largest combination with distinct elements is tuple7 and tuple8.

[jorge arenas molina]

You can install tuples from SSC, then extract all combinations and specify a condition to check repetitions within observations (rows). Let me know if you have difficulties doing this. For my example:

*ssc install tuples
tuples a1b1 a1b2 a2b1 a2b2
macro list

Res.:

_ntuples: 15
_tuple15: a1b1 a1b2 a2b1 a2b2
_tuple14: a1b1 a1b2 a2b1
_tuple13: a1b1 a1b2 a2b2
_tuple12: a1b1 a2b1 a2b2
_tuple11: a1b2 a2b1 a2b2
_tuple10: a1b1 a1b2
_tuple9: a1b1 a2b1
_tuple8: a1b1 a2b2
_tuple7: a1b2 a2b1
_tuple6: a1b2 a2b2
_tuple5: a2b1 a2b2
_tuple4: a1b1
_tuple3: a1b2
_tuple2: a2b1
_tuple1: a2b2

A search will reveal that the largest combination with distinct elements is tuple7 and tuple8.

Hi Andrew,

Thank you very much for the answer, it is precisely what I was looking for. However, I still cannot set the criteria to only leave tuples that do not contain elements in common. I checked the help of the tuples command, but I can't bring this restriction to the language of conditionals. Can you guide me on this? I will apreciate a lot.

Best,

[Clyde Schechter]

Your restriction does not define a unique subset C of A x B. For example, suppose A = {a1, a2} and B = {b1, b2}. Then C = {(a1, b1), (a2, b2)} satisfies your restriction: nothing can be added because all members from A and B have already appeared somewhere in an ordered pair in C. But, C' = {(a1, b2), (a2, b1)} is another subset, in fact it is disjoint from C, that also satisfies the same condition.

You can answer your question about how many such C's there are purely from combinatorics; there is no need to simulate this on a computer. In full generality, if A has m elements and B has n elements, let r = min(m, n). Choose r elements from each of A and B. Establish a bijection, f: A -> B (any bijection wlil do, there are r! of them) and create C as the set of of pairs (a, f(A)) where a ranges over the r elements chosen from A. The resulting C satisfies your restriction. The number of ways of doing this is quite large. If, for example, A is the smaller set, then there is just one way to choose the elements of A, since all are chosen. But then there are mCr ways to choose the elements of B, and r! bijections. If B is larger, it's the same thing with the roles of A and B reversed. So the total number of possible subsets C is sCr X r!, where s = max(m, n). And all such sets C must contain exactly r ordered pairs: there cannot be more without duplicating some element of the smaller set, nor can there be less since, then, nothing would block one from adding another ordered pair made from an unused element of A and an unused element of B.

[Andrew Musau]

Hi Andrew,

Thank you very much for the answer, it is precisely what I was looking for. However, I still cannot set the criteria to only leave tuples that do not contain elements in common. I checked the help of the tuples command, but I can't bring this restriction to the language of conditionals. Can you guide me on this? I will apreciate a lot.

Best,

I was not clear in #4. What I meant by specifying a condition is to extract all tuples and find the largest tuple (tuples) that has (have) unique elements. Clyde has nicely illustrated how you count how many of these exist. Here is a way to extract them. Note that the condition that I specify below is that a unique element of the set ends in a digit which is followed by a non-digit (a letter or space in this instance). Your condition may be different depending on how your elements in the Cartesian product are named.

tuples a1b1 a1b2 a2b1 a2b2
clear
set obs `ntuples'
gen which=_n
gen tuple=""
forval i=1/`ntuples'{
    replace tuple = "`tuple`i''" in `i'
}
gen intuple= ustrregexra(tuple, "([\d])([^\d])", "$1,")
split intuple, p(,) g(e)
drop intuple
reshape long e, i(tuple which) j(element)
replace e= strtrim(e)
drop if missing(e)
duplicates tag which e, gen(dup)
egen tag= tag(which)
bys which: egen hasdups=max(dup>0)
bys which: gen size=_N
egen max= max(size) if !hasdups
list tuple which if tag&size==max, sep(0)

Res.:

. list tuple which if tag&size==max, sep(0)

     +-------------------+
     |     tuple   which |
     |-------------------|
 19. | a1b2 a2b1       7 |
 23. | a1b1 a2b2       8 |
     +-------------------+

[Andrew Musau]

Each added element in a set vastly expands the number of combinations. For example, adding an element such that \( A= \{a_1, a_2, a_3\}\) and \( B= \{b_1, b_2, b_3\}\), you have 100+ combinations.

tuples a1b1 a1b2 a1b3 a2b1 a2b2 a2b3 a3b1 a3b2 a3b3
clear
set obs `ntuples'
gen which=_n
gen tuple=""
forval i=1/`ntuples'{
    replace tuple = "`tuple`i''" in `i'
}
gen intuple= ustrregexra(tuple, "([\d])([^\d])", "$1,")
split intuple, p(,) g(e)
drop intuple
reshape long e, i(tuple which) j(element)
replace e= strtrim(e)
drop if missing(e)
duplicates tag which e, gen(dup)
egen tag= tag(which)
bys which: egen hasdups=max(dup>0)
bys which: gen size=_N
egen max= max(size) if !hasdups
list tuple which if tag&size==max, sep(0)

Res.:

. list tuple which if tag&size==max, sep(0)

      +------------------------+
      |          tuple   which |
      |------------------------|
 336. | a1b3 a2b2 a3b1      74 |
 349. | a1b3 a2b1 a3b2      77 |
 407. | a1b2 a2b3 a3b1      86 |
 437. | a1b2 a2b1 a3b3      91 |
 527. | a1b1 a2b3 a3b2     106 |
 540. | a1b1 a2b2 a3b3     108 |