17 Feb
2010
17 Feb
'10
12:01 p.m.
* 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).