A slick way to generate permutations is via a sequence of adjacent transpositions [usually credited to Trotter and Johnson, though some authors claim it predates these publications]. Most implementations seem to rely on maintaining at least one global array, say s_k = +1,-1 according to whether symbol k is currently transposing rightwards, leftwards along the array of n symbols; Revisiting this recently, I noticed that an array is unnecessary: all that is required is a single binary digit containing the parity of the current permutation; then the other parities required --- of the partial permutations of symbols k,...,n --- can be efficiently deduced as required. But it does not seem easy to extirpate this final bit, without committing the algorithm to an O(n log n) computation at every call in order to find the parity, essentially by sorting the permutation. Is there an O(n) algorithm for parity of a permutation? If not, why not? Fred Lunnon