OK, let me see if I understand this. We write a permutation P on the integers [1...n] as (P(1), P(2), ..., P(n)). If we cut this sequence off prematurely, at only k elements, k < n, we get a proper prefix. This is not typically a permutation itself, but sometimes it is; if this is the case, the permutation is not connected. A connected permutation is one that has no "cut"; for all k < n, the prefix of length k contains an integer greater than k. The reason it took me a long time to figure out what we were talking about is that this is not really a group-theoretic property, and my reflex is to think of permutations as elements of a group; in the algebraic context, the objects being permuted are abstract frobs, which can be labeled with integers or letters or anything else. Another way to say this is that you can have two similar permutations, indistinguishable algebraically, only one of which is "connected". If a permutation is not the identity, it is always similar to a connected permutation; to prove this, pick any moving element x, and label x as "1" and P(x) as "n". Then the representation of P begins with an n, guaranteeing connectedness. On Wed, Feb 17, 2010 at 2:02 PM, Joerg Arndt <arndt@jjj.de> wrote:
* Schroeppel, Richard <rschroe@sandia.gov> [Feb 17. 2010 19:49]:
What's "connected"? Everything in one big cycle? --Rich
A permutation is "connected" if no proper prefix is mapped to itself.
Test: compute maxima of all proper prefixes (cost is O(n)) and check the current max (for, say, length-k prefix) is greater than k (assuming you permute [1,2,...,n]).
The name "connected" may reflect that a non-connected permutation can be written as concat of two perms ( P1(prefix) . P2(suffix) ), but then maybe it's just another name as stupid as "root system".
"one big cycle" perms are "cyclic" perms (which, together with "all permutations" are trivial to create unbiased).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun