# Count all binary relations

## APL (Dyalog Extended), ^{99} 93 bytes

```
r←0∊0 0⍉⊢
R←r~
s←⊢≢⍉
S←1∊⊢∧⍉
t←0∊⊢≥∨.∧⍨
T←1∊⊢∧∨.∧⍨
{×⍵:+/∧⌿~(⍺,'0'){(⍎⍺)⊣⍵}\⍵-⍛↑∘⊤¨,⍳⍵⍴2*⍵⋄1}
```

Try it online!

-5 bytes thanks to @ovs for spotting `R←r~`

, and -1 by taking the boolean negation of the intermediate results.

Takes the condition as a string, using the abbreviation as follows:

```
r: reflexive
R: irreflexive
s: symmetric
S: asymmetric
t: transitive
T: antitransitive
```

For example, reflexive + symmetric + transitive is given as `'rst'`

and "no condition" is given as `''`

.

### How it works (before golfing)

```
⍝ Each of rRsStT takes an adjacency matrix and determines if the condition is met
⍝ reflexive: the diagonal is all ones
r←∧/0 0⍉⊢
⍝ irreflexive: the diagonal is all zeros
R←∧/0 0⍉~
⍝ symmetric: transpose is equal to self
s←⊢≡⍉
⍝ antisymmetric: each position in self and transpose cannot be both ones
S←~1∊⊢∧⍉
⍝ transitive: self includes the transitive square of self
t←~0∊⊢≥∨.∧⍨
⍝ antitransitive: each position in self and transitive square cannot be both ones
T←~1∊⊢∧∨.∧⍨
⍝ main function
{×⍵:+/∧⌿(⍺,'≡'){(⍎⍺)⍵}\⍵-⍛↑∘⊤¨,⍳⍵⍴2*⍵⋄1} ⍝ ⍵: n, ⍺: conditions
{×⍵: ... ⋄1} ⍝ Take 0 as a special case, always returning 1
,⍳⍵⍴2*⍵ ⍝ Generate all length-n vectors of 0..2^n-1
⍵-⍛↑∘⊤¨ ⍝ Convert them to n×n binary matrices
(⍺,'≡') ⍝ Add a default function that always returns 1 to the list of conditions
{...}\ ⍝ Take outer product of conditions and matrices...
(⍎⍺)⍵ ⍝ Eval the condition function and apply it to the matrix
+/∧⌿ ⍝ Count the matrices which satisfy all the conditions
```

## JavaScript (Node.js), 182 bytes

A slower but significantly shorter version suggested by @tsh.

Expects `(n)(m)`

, where **n** is a BigInt and **m** is a list of constraints among:

```
IRREFLEXIVE = 0, REFLEXIVE = 1, ANTISYMMETRIC = 2,
SYMMETRIC = 3, ANTITRANSITIVE = 4, TRANSITIVE = 5
```

```
n=>m=>eval("g=(c,x=n)=>x?c(--x)&g(c,x):1;h=(x,y)=>!(k>>x+n*y&1n);for(t=0,k=1n<<n*n;k--;)t+=m.every(q=>g(x=>g(y=>g(z=>[h(x,x)^q,h(x,y)|h(y,x)^q%2,h(x,y)|h(y,z)|h(x,z)^q%2][q>>1]))))")
```

Try it online! (part 1)

Try it online! (part 2)

## JavaScript (Node.js), 215 bytes

Expects `(n)(m)`

, where **n** is a BigInt and **m** is a bit-mask describing which constraints are enabled, using a combination of:

```
IRREFLEXIVE = 1
REFLEXIVE = 2
ANTISYMMETRIC = 4
SYMMETRIC = 8
ANTITRANSITIVE = 16
TRANSITIVE = 32
```

```
n=>m=>{g=(c,x=n)=>x?c(--x)&g(c,x):1;h=(x,y)=>!(k>>x+n*y&1n);for(t=0,k=1n<<n*n;k--;)t+=![x=>h(x,x)^q,0,x=>g(y=>h(x,y)|h(y,x)^q),0,x=>g(y=>g(z=>h(x,y)|h(y,z)|h(x,z)^q)),0].some((c,j)=>m>>j&!g((q=j&1)?C:C=c));return t}
```

Try it online!

Notes:

- To get a much faster version, replace the first bitwise
`&`

with`&&`

. - Using BigInts is slower and slightly longer, but allows this code to work for any
**n**in theory.

### Formatted and commented

```
n => m => {
// helper function to test whether c(x) is true for all x in [0 .. n - 1]
g = (c, x = n) => x ? c(--x) & g(c, x) : 1;
// helper function to test if (x, y) is *not* in S
h = (x, y) => !(k >> x + n * y & 1n);
// we use k = 2 ** n² - 1 to k = 0 to describe all possible binary relations
// (k is essentially a flatten binary matrix of size n x n)
for(t = 0, k = 1n << n * n; k--;)
// increment t if ...
t +=
// ... the following tests are all falsy
![
// irreflexive (q = 0) / reflexive (q = 1)
x => h(x, x) ^ q, 0,
// antisymmetric (q = 0) / symmetric (q = 1)
x => g(y => h(x, y) | h(y, x) ^ q), 0,
// antitransitive (q = 0) / transitive (q = 1)
x => g(y => g(z => h(x, y) | h(y, z) | h(x, z) ^ q)), 0
]
.some((c, j) =>
// return true if the constraint is set ...
m >> j &
// ... and the test fails
!g((q = j & 1) ? C : C = c)
);
return t
}
```

## Python 3, 319 bytes

Expects to be called as `f(n, m)`

, where m is a bitmask of which conditions are required, in the same order as the question.

```
r=lambda x:x and r(x[1:])+[x[:1]+a for a in r(x[1:])]or[[]]
f=lambda n,c:(lambda z:n==0 or sum(1for a in map(set,r([(x,y)for x in z for y in z]))if not(lambda g,h,i:(g<=a)+(a-g==a)*2+(h==a)*4+(a-h==a)*8+(i|a==a)*16+(a-i==a)*32)(set(zip(z,z)),{(q,b)for(b,q)in a},{(d,c)for(d,b)in a for(l,c)in a if l==b})&c^c))(range(n))
```

Try it online!