Indeed, I hadn't thought much about representation --- just employed the obvious list of n integers in the range 1,...,n, and costing operations on integers, as you say. Thanks for the algorithm, which I certainly wouldn't have found easily, if at all --- thanks too for Mike Speciner's documentation [noticeably absent from the original, as with most code posted by enthusiasts!]. I realised in the meantime that the adjacent transposition algorithm can be improved from time O(n) to average constant time, at the cost of retaining a counter of permutations previously generated. Its residue mod 2 gives the parity, hence the direction of transpostion; dividing by n...(n-j+1) gives the sub-counter for symbols j,...,n; the final remainder gives the position of the symbol j = k to be transposed. Since k = 1 for all but a fraction 1/n of calls, the average time is now essentially independent of n --- indeed, decreases with it! Fred Lunnon On 12/17/06, Pacher Christoph <Christoph.Pacher@arcs.ac.at> wrote:
I suppose that algorithm is O(n) if you take as O(1) examining a number with log n bits.
yes, I am thinking this is what Fred had in mind, because he was talking about an O(n log n) algorithm which "essentially sorts the permutation". And sorting integers takes O(n log n) comparisons and swaps of integers (not bits).
But I might be completely wrong, Fred?
Christoph
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun