| Bytes | Lang | Time | Link |
|---|---|---|---|
| 117 | JavaScript ES6 | 250319T173121Z | Arnauld |
| 025 | Uiua | 250323T120520Z | Joao-3 |
| 080 | Maple | 250321T045107Z | dharr |
| 098 | Python | 250320T125718Z | Albert.L |
| 103 | Python | 250319T193250Z | Mukundan |
| 048 | Charcoal | 250319T225358Z | Neil |
| 009 | Jelly | 250319T183325Z | Jonathan |
| 134 | Python3 | 250319T172346Z | Ajax1234 |
JavaScript (ES6), 117 bytes
The output is 0-indexed: \$\mathcal I_n = \mathcal I_{\{0, 1, ..., n-1\}}\$.
n=>(g=(k,a=[],b=a)=>k--?[...g(k,a,b),...a[I="includes"](y=k/n|0)|b[I](x=k%n)?[]:g(k,[y,...a],[x,...b])]:[[a,b]])(n*n)
Uiua, 25 bytes
/◇⊂⍚(≡□♭₃⊞⊟⊃⧅<⧅≠⊙↘₁)⟜¤⇡+1
Outputs a list of boxed matrices representing the mappings.
This type of challenge is why the ⧅ tuples modifier is so helpful; it can generate combinations and permutations.
Maple, 80 bytes
n->[seq(seq(seq([i,j],j=c:-permute(n,k)),i=(c:=combinat):-choose(n,k)),k=0..n)];
Output format as for test cases in the question. Inputs are combinations of size k, each has outputs that are permutations of the same size.
Python, 98 bytes
lambda n:(m:=n+1)and{(*sorted({p//m**z%m:z+1for z in range(m)}.items())[1:],)for p in range(m**n)}
Returns a set of tuples of pairs.
How?
Uses the Python set and dict data types to eliminate duplicates where needed.
Using @xnor's proposed output format:
Python, 76 bytes
f=lambda n,*o:[*o,o][n:]or sum([f(n,j,*o)for j in{*range(1,n+1)}^{*o,0}],[])
Python, 106 104 103 bytes
f=lambda n,a=0,b={0}:[k|{i+1:j}for i in range(a,n)for j in{*range(n+1)}-b for k in f(n,i+1,b|{j})]+[{}]
Returns a list of dictionaries containing the mappings
Python, 70 bytes
lambda n:{*permutations([*range(n+1)]+[0]*n,n)}
from itertools import*
Outputs the mapping as a list where each element is mapped to its corresponding index and zeros aren't mapped; output format was suggested in a comment by @xnor to the question
I do feel like this output format is a bit cheaty
Charcoal, 48 bytes
Nθ⊞υ⟦⟦⟧⟦⟧⟧FυF⎇§ι⁰⌊§ι⁰θF⁻…⁰θ§ι¹⊞υEι⁺μ⟦⎇νλκ⟧E⊕υ⭆¹ι
Try it online! Link is to verbose version of code. Explanation:
Nθ
Input n.
⊞υ⟦⟦⟧⟦⟧⟧
Start with the empty map.
Fυ
Loop over all of the maps as they are discovered.
F⎇§ι⁰⌊§ι⁰θ
Loop over the values up to the minimum x value in the map.
F⁻…⁰θ§ι¹
Loop over the unused y values in the map.
⊞υEι⁺μ⟦⎇νλκ⟧
Add a new map adding that x→y mapping.
E⊕υ⭆¹ι
Pretty-print the maps. Note that I've added a ⊕ to output the map as 1-indexed; on TIO this also has the effect of outputting the empty map as None instead of [].
Jelly, 9 bytes
œcpœ!ɗⱮŻẎ
A monadic Link that accepts a positive* integer, \$n\$, and yields the symmetric inverse semigroup of the first \$n\$ natural numbers.
* also works for \$n=0\$, yielding the expected list of the single, empty mapping [[[], []]]
How?
œcpœ!ɗⱮŻẎ - Link: non-negative integer, N
Ż - zero-range {N} -> [0..N]
Ɱ - map across {Size in [0..N]} with:
ɗ - last three links as a dyad - f(N, Size):
œc - {[1..N]} combinations without replacement {Size}
-> C = unordered lists of length Size from alphabet [1..N]
œ! - {[1..N]} permutations without replacement {Size}
-> P = ordered lists of length Size from alphabet [1..N]
p - {C} Cartesian product {P}
-> all mappings for [1..N] of domain cardinality Size
Ẏ - tighten to a single list of mappings at all values of Size
Python3, 134 bytes
from itertools import*
def f(n):
t=[*range(1,n+1)]
return[0]+[[j,k]for i in t for k in permutations(t,i) for j in combinations(t,i)]