  While there has been significant progress on algorithmic aspects of the
Lov\'{a}sz Local Lemma (LLL) in recent years, a noteworthy exception is when
the LLL is used in the context of random permutations. The breakthrough
algorithm of Moser & Tardos only works in the setting of independent variables,
and does not apply in this context. We resolve this by developing a randomized
polynomial-time algorithm for such applications. A noteworthy application is
for Latin transversals: the best-known general result here (Bissacot et al.,
improving on Erd\H{o}s and Spencer), states that any $n \times n$ matrix in
which each entry appears at most $(27/256)n$ times, has a Latin transversal. We
present the first polynomial-time algorithm to construct such a transversal. We
also develop RNC algorithms for Latin transversals, rainbow Hamiltonian cycles,
strong chromatic number, and hypergraph packing.
  In addition to efficiently finding a configuration which avoids bad-events,
the algorithm of Moser & Tardos has many powerful extensions and properties.
These include a well-characterized distribution on the output distribution,
parallel algorithms, and a partial resampling variant. We show that our
algorithm has nearly all of the same useful properties as the Moser-Tardos
algorithm, and present a comparison of this aspect with recent works on the LLL
in general probability spaces.
