While there has been significant progress on algorithmic aspects of the Lová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 general result known here (Bissacot et al., improving on Erdő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 $\cclass{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 work on the LLL in general probability spaces.

An extended abstract of this paper has appeared in the Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, 2014.