🚀 go-pugleaf

In article <greil.726829446@guug.de> greil@guug.de (Anton Greil) writes:
>mnewman@comlab.ox.ac.uk (Matthew Newman) writes:
>
>>Does anyone know the status on the following problem ?
>
>>Let S(n) be the set of all permutations of the integers 1..n
>>Let T(n) be the set of all transpositions (i.e. swapping
>>two numbers).
>
>>For which n can one find a set B(n) such that for all p in S(n)
>>either p is in B(n), or p differs by exactly one transposition
>>from an element of B(n), and such that no two elements from B(n)
>>differ by exactly one transposition ?

All n.  Take B(n) = A(n), the alternating subgroup of S(n) consisting
of all even permutations of S(n).  (The other coset, S(n)-A(n), will do
equally well.)  Every even permutation is in B(n), every odd
permutation is one transposition away from an element of B(n), and any
two elements of B(n) are at least two transpositions apart.

>
>I'd like to append with a more general question:
>
>T(n) forms a generating system for S(n)  (for all n).
>How can the combinatorics of this generating system be characterized?

T(n) constitutes the edges of a regular undirected graph on S(n) (all
vertices have the same degree).  The distance between p and q is n-c
where c is the number of cycles in pq^-1.  (Proof: by induction on
distance.  The identity has n cycles, and every transposition increases
or decreases the number of cycles by 1.)  Hence the diameter is n-1,
with those p,q for which pq^-1 is cyclic being antipodal.

>Especially: does there exist a normal form of each generated element from
>S(n) over the base T(n) ?

The following normal form minimizes number of transpositions.

To form (A1 A2 ... An), for each i from 1 to n-1, transpose i and Ai if
necessary.  E.g. to form (4 2 1 3) start from (1 2 3 4) and proceed thus:

	Transposition	  Result
			(1 2 3 4)
	1 <-> 4 	(4 2 3 1)
	2 <-> 2		unnecessary
	3 <-> 1		(4 2 1 3)

This can be seen to achieve the above distance n-c, and hence is is
minimal.

Another normal form is to implement each cycle starting from the least
element of each cycle.  This is just a permutation of the above normal
form: any two noninterfering transpositions (transposition pairs
involving four locations) commute, in particular transpositions from
distinct cycles.  Hence it is equally efficient.
-- 
Vaughan Pratt			There's safety in large condition numbers.