I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself. More precisely, suppose that $A$ and $B$ are not known, but only an element $a\in A$, then it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is not possible with this definition.
On the other hand, this allows algorithms whose welldefinedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.
Let me contrast this definition with other concepts, which I believe
should be orthogonal to being explicit.
computational complexity: a bijection may be computable in
polynomial time and memory, but still be not explicit.
For example, Dyck paths of semilength $n$ with exactly one valley are
in bijection with subsets of size $2$ in $\{1,\dots,n\}$. A
nonexplicit bijection which is computable in polynomial time is to
fix an order on the Dyck paths, and an order on the subsets and match
elements with the same index.
simplicity: a bijection may be very complicated, but still be
explicit.
A (biased) example is Jagenteufel's bijection between Riordan paths
and standard Young tableaux with three rows, whose row lengths are
either all odd or all even, see Algorithm 3 in
https://arxiv.org/abs/1801.03780, or Algorithm 3 in
https://arxiv.org/abs/1902.03843 for a generalisation to fans of
Riordan paths.
Although this bijection is really complicated, it allows to deduce a
refinement of the equinumeration result, that is otherwise
unavailable.
apparently bijective:
The sweep maps on lattice paths were defined by Armstrong, Loehr and
Warrington in https://arxiv.org/abs/1406.1196. It took quite a while
to show that they are bijective, see Thomas and Williams
https://arxiv.org/abs/1512.01483. I think that the maps were
bijective already in June 2014, and did not become bijective in
December 2015, but philosophy might disagree.
I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties.
apparently well defined:
Consider Prüfer's bijection between $(n2)$tuples of integers in
$\{1,\dots,n\}$ and labelled trees on $n$ vertices. Although not
hard to see, it is not a priori clear that given a tuple one actually
obtains a tree: from the definition of the algorithm itself one might
think that the result could be forest.
I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself. More precisely, suppose that $A$ and $B$ are not known, but only an element $a\in A$, then it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is not possible with this definition.
On the other hand, this allows algorithms whose welldefinedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.
I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself. More precisely, suppose that $A$ and $B$ are not known, but only an element $a\in A$, then it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is not possible with this definition.
On the other hand, this allows algorithms whose welldefinedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.
Let me contrast this definition with other concepts, which I believe
should be orthogonal to being explicit.
computational complexity: a bijection may be computable in
polynomial time and memory, but still be not explicit.
For example, Dyck paths of semilength $n$ with exactly one valley are
in bijection with subsets of size $2$ in $\{1,\dots,n\}$. A
nonexplicit bijection which is computable in polynomial time is to
fix an order on the Dyck paths, and an order on the subsets and match
elements with the same index.
simplicity: a bijection may be very complicated, but still be
explicit.
A (biased) example is Jagenteufel's bijection between Riordan paths
and standard Young tableaux with three rows, whose row lengths are
either all odd or all even, see Algorithm 3 in
https://arxiv.org/abs/1801.03780, or Algorithm 3 in
https://arxiv.org/abs/1902.03843 for a generalisation to fans of
Riordan paths.
Although this bijection is really complicated, it allows to deduce a
refinement of the equinumeration result, that is otherwise
unavailable.
apparently bijective:
The sweep maps on lattice paths were defined by Armstrong, Loehr and
Warrington in https://arxiv.org/abs/1406.1196. It took quite a while
to show that they are bijective, see Thomas and Williams
https://arxiv.org/abs/1512.01483. I think that the maps were
bijective already in June 2014, and did not become bijective in
December 2015, but philosophy might disagree.
I am sure there are also examples where the only known proof of bijectivity uses enumeration, but the map itself yields other properties.
apparently well defined:
Consider Prüfer's bijection between $(n2)$tuples of integers in
$\{1,\dots,n\}$ and labelled trees on $n$ vertices. Although not
hard to see, it is not a priori clear that given a tuple one actually
obtains a tree: from the definition of the algorithm itself one might
think that the result could be forest.

I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself.
In particular More precisely, I believesuppose that one should$A$ and $B$ are not require that welldefinedness or injectivity is obvious from the algorithm.
Unfortunatelyknown, I am unable to make the phrase 'without reference tobut only an element $B$' precise. However$a\in A$, to illustratethen it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is clearly not allowedpossible with this definition.
On the other hand, this allows algorithms whose welldefinedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.
I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself.
In particular, I believe that one should not require that welldefinedness or injectivity is obvious from the algorithm.
Unfortunately, I am unable to make the phrase 'without reference to $B$' precise. However, to illustrate it, sorting $B$, or iterating over $B$ to find a particular object, is clearly not allowed.
I would say that a bijection $\pi: A\to B$ is explicit, if for every $a\in A$ the image $\pi(a)$ can be computed without reference to $B$ itself. More precisely, suppose that $A$ and $B$ are not known, but only an element $a\in A$, then it should still be possible to construct $\pi(a)$.
In particular, sorting $B$, or iterating over $B$ to find a particular object, is not possible with this definition.
On the other hand, this allows algorithms whose welldefinedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.
