I'm not sure if I'm helping, but I'm also not sure if I understand what
you are saying.
Let us fix a set X we are considering the permutation group of, below I
will take X = {1, 2, 3, 4, 5}. A permutation of X is by definition a
bijective function f:X->X. It is specified uniquely by providing the
image of every element. We can write this in the short form
[f(1), f(2), f(3), f(4), f(5)]. In this way, every permutation is
represented by an array of constant size.
Now let's talk about cycles. By definition, a cycle is an ordered subset
of X. In general, the cycle (a_1 ... a_n) represents the unique
permutation f with f(a_1) = a_2, ..., f(a_n) = a_1, and f(x) = x for all
x not in {a_1, .., a_n}. For example, the cycle (1 2 3) denotes the
permutation [2, 3, 1, 4, 5].
We can identify the set of cycles with a subset of the set of permutations.
Now let's consider composition. There are two schools of thought. Let me
write * for "ordinary" (where I come from) composition, and . for
"weird" composition. By definition, if f, g are permutations, then the
permutation f*g is the unique mapping such that (f*g)(x) = f(g(x))
["apply right to left"], whereas (f.g)(x) = g(f(x)) ["apply left to
right"]. [*]
Observe now that any permutation can be written uniquely (up to
ordering) as a product of disjoint cycles. That is, if f is any
permutation, then there exists distinct and disjoint cycles c_1, ..,
c_n, such that c_1*...*c_n = f = c_1.c_2 ... .c_n [i.e. the two modes of
composition agree for disjoint cycles]. Moreover the order of
composition is irrelevant, and if d_1, .., d_m are another set of
disjoint cycles usch that f = d_1, .., d_m then {c_1, .., c_n} = {d_1,
.., d_m} [in particular n = m].
Finally, composition of cycles. Since we have already defined
composition of permutations (in fact in two ways), and since finding the
disjoint cycle composition of a permutation is easy, there is actually
not much to say here. Let's just consider an example:
(1 2 3)*(3 4 5) = (1 2 3 4 5) = [2, 3, 4, 5, 1]
(1 2 3).(3 4 5) = (1 2 4 5 3) = [2, 4, 1, 5, 3]
I can see the cycles easily as follows: in either case, I first write
down the 1. Then I figure out where 1 is mapped. In the first case, (3 4
5) is applied first, which fixes 1, and then (1 2 3) is applied, which
maps 1 to 2, so 1 is mapped to 2. In the second case 1 is first mapped
to 2 and then 2 is fixed, so same effect. Now to continue the cycle, I
figure out where 2 is mapped. In the first case, (3 4 5) fixes 2, and
then (1 2 3) maps it to 3, so 2 is mapped to 3. In the second case, (1 2
3) maps 2 to 3, and then (3 4 5) maps 3 to 4. Hence 2 is mapped to 4.
In the first case I continue by figuring out where 3 is mapped, in the
second by figuring out where 4 is mapped.
I'm writing this chiefly because it shows that, in "ordinary" (right to
left) composition, the cycle notation is obtained by reading right to
left! Similarly in left to right composition you read cycles left to right.
Probably all this is obvious to you, and I'm just misreading your statement.
[*] Note that this can be made to look more sensible (for some
definitions of sensible), by writing *arguments* on the left: applying f
to x can be written as (x)f, and then (x)(f.g) = ((x)f)g ...
On 27.08.2012 17:05, Chris Smith wrote:
I guess it'd be better to make g*h mean "first apply g, then h", since
that's how other CAS that handle permutations do it.
According to David, this is not the case. e.g. in gap (1, 2)*(2, 3)
gives a R to L multiplication of those cycles.
I would call gap's method L or R: first see what happens to 1 as you
scan left to right:
1 goes to 2 which goes to 3, so 1 goes to 3, etc, This gives (1,3,2).
Very interesting way to look at it. Since I am looking at these as
shorthand for permutations, and you get the correct answer by applying
the rightmost permutations first. But if you think of trying to find
the correct cycle notation, you do so by reading left to right. So
perhaps the docstring should say that products of disjoint cycles
computes the product of the corresponding permutations from right to
left.
Note that at least one author (
http://www.usna.edu/Users/math/wdj/tonybook/gpthry/node13.html ) gets
this wrong, reconstructing the *cycle* by reading right to left. To
get the right permutation, apply permutations from right to left for a
given cycle notation; to get the cycle notation correct, read from
left to right. The example is
(1,2)*(2,4,5)*(1,3)*(1,2,5)
Here are the permutations (in left to right order) starting after the
identity with the result of applying that to the previous result:
[0, 1, 2, 3, 4, 5]
[0, 2, 1, 3, 4, 5] -> [0, 2, 1, 3, 4, 5]
[0, 1, 4, 3, 5, 2] -> [0, 2, 4, 3, 5, 1]
[0, 3, 2, 1, 4, 5] -> [0, 3, 4, 2, 5, 1]
[0, 2, 5, 3, 4, 1] -> [0, 4, 1, 2, 5, 3]
That answer, in cyclic form is, [[1, 4, 5, 3, 2]]. This is the result
you get when you process permutations from left to right or read cycle
notation from right to left.
If you do the reverse (apply permutations from right to left) or
cycles from left to right you get [[1, 4], [2, 3]] .
I'll add a note to the documentation.
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
