Re: [math-fun] Optimally sorting a cyclic group
Let C_n denote the cyclic group Z/nZ, and let s : C_n —> C_n be any permutation of C_n. Question: Is there in some sense always a "nearest" rotation of C_n (i.e., a translation by a group element) to the permutation s, in a consistent manner. I.e., such that for any rotation R of C_n we have nearest(s) = R*nearest(R*s). or in group notation nearest(s) + g = g + nearest(L_g+s) That is, the nearest rotation to [a permutation s followed by a rotation R] is the result of applying the rotation R to [the nearest rotation to the permutation s]. —Dan Henry Baker wrote: ----- Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1). ... However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better? -----
participants (1)
-
Dan Asimov