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 well-definedness 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 well-definedness 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 non-explicit 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 $(n-2)$-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, I believe that one should not require that well-definedness 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 well-definedness or injectivity is not obvious from the algorithm. I think that this is in fact desirable.