Re: Design query: Ev2 and multiple moves

On Saturday, November 05, 2011 8:21 PM, "Greg Stein" <gstein_at_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? :-)
Received on 2011-11-06 06:38:05 CET