  The Ulam distance of two permutations on $[n]$ is $n$ minus the length of
their longest common subsequence. In this paper, we show that for every
$\varepsilon>0$, there exists some $\alpha>0$, and an infinite set
$\Gamma\subseteq \mathbb{N}$, such that for all $n\in\Gamma$, there is an
explicit set $C_n$ of $(n!)^{\alpha}$ many permutations on $[n]$, such that
every pair of permutations in $C_n$ has pairwise Ulam distance at least
$(1-\varepsilon)\cdot n$. Moreover, we can compute the $i^{\text{th}}$
permutation in $C_n$ in poly$(n)$ time and can also decode in poly$(n)$ time, a
permutation $\pi$ on $[n]$ to its closest permutation $\pi^*$ in $C_n$, if the
Ulam distance of $\pi$ and $\pi^*$ is less than $ \frac{(1-\varepsilon)\cdot
n}{4} $.
  Previously, it was implicitly known by combining works of Goldreich and
Wigderson [Israel Journal of Mathematics'23] and Farnoud, Skachek, and
Milenkovic [IEEE Transactions on Information Theory'13] in a black-box manner,
that it is possible to explicitly construct $(n!)^{\Omega(1)}$ many
permutations on $[n]$, such that every pair of them have pairwise Ulam distance
at least $\frac{n}{6}\cdot (1-\varepsilon)$, for any $\varepsilon>0$, and the
bound on the distance can be improved to $\frac{n}{4}\cdot (1-\varepsilon)$ if
the construction of Goldreich and Wigderson is directly analyzed in the Ulam
metric.
