On Saturday, November 05, 2011 8:21 PM, "Greg Stein" <gst...@gmail.com> wrote: > [ how to move A1->A2->A3->...->An->A1 circularly in a single txn ] ... > I'm not a master of topography or graphs, but I suspect that any given > permutation of N nodes can be reduced to a set of rotations of subsets > of those N nodes. Thus, a general "rotate" API should be sufficient.
That's correct. Any permutation on N nodes can be described uniquely as the composition of pairwise-disjoint cycles of 1..N nodes each. Furthermore, any cycle can be described as the composition of (non- disjoint) 2-element swaps. In this context, "cycle" is a cyclic permutation such as 1->3->7->1, and "composition" is normal function composition, aka product of permutations. Composition of disjoint cycles is commutative. Any more group theory questions this morning? :-)
