Re: Challenae question for mathematician

[CC'ed to poster]

surprisinggift@xxxxxxxxx wrote:
I am looking for a method to calculating the similar of the "order" of
a sequence of number

e.g. we have three ordered number sequences

a) 1 2 4 3 5
b) 1 2 3 4 5
c) 1 2 5 4 3

So here, seqence a) is more closer to b) than c). because there is only
one neighbor switch of two numbers

Is there an existing way to calculate this similarity?

Well, the transpositions (i,i+1), i=1,...,n-1 generate S_n, the full
permutation group on n elements.
You can think of (a), (b), and (c) as permutations in S_n: (a) is the
permutation sending 1 to 1, 2 to 2, 3 to 4, 4 to 3, and 5 to 5 (i.e.,
(3,4)); (b) is the identity permutation; and (c) is the permutation
(3,5).

The "distance" from (a) to (b) can be considered to be (a)(b)^{-1}
(viewed as permutations).

If we let S = { (1,2), (2,3), (3,4), ..., (n-1,n) }.

We can express (a)(b)^{-1} = (3,4) as a product of elements of S by

(3,4) = (3,4).

You can express (c)(b)^{-1} = (3,5) as a product of elements of S by

(3,5) = (3,5)(4,5)(3,4) [composing right to left]

For an element x of S_n, define its S-length to be the least number of
factors needed to express x as a product of elements of S. Define the
"distance" from x to y, d(x,y) to be the length of xy^{-1}.

Note that d(x,x) = 0, and d(x,y)=d(y,x) (the latter since the elements
of S are their own inverses).
And if d(x,y)=0, then x=y.

If x, y, and z are any three elements, then d(x,y) + d(y,z) >= d(x,z),
since any expression of xy^{-1} as a product of elements of S,
concatenated with an expression of yz^{-1} as a product of elements of
S will yield an expression that equals xz^{-1}, though there may be
cancellations making the distance from x to z smaller.

So this gives you a notion of "distance" in the usual sense, and it
seems to measure exactly what you want: how many swaps of adjacent
terms are needed to go from one list to the other.

There are a lot of algorithms for permutation groups, so it should be
relatively straighforward to find the S-length of any given element,
which will give what you want (assuming I interpreted this correctly.

Arturo Magidin, sans .sig

.

Relevant Pages