[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Design query: Ev2 and multiple moves

From: Daniel Shahaf <d.s_at_daniel.shahaf.name>
Date: Sun, 06 Nov 2011 07:37:28 +0200

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

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.