Cycles of a permutation: Difference between revisions

Content added Content deleted
m (replaced ⋅ with ∙)
Line 71: Line 71:
Thu->Wed: (2 4 14 5 15 10 11 3 7 8) (9 13 12)
Thu->Wed: (2 4 14 5 15 10 11 3 7 8) (9 13 12)
If Alf and Betty went to visit Anna and Graham on a Wednesday and came home on a Friday, they'd need to figure out the permutation Wed->Fri from the permutations Wed->Thu and Thu->Fri. Mathematicians call this either composition or multiplication, and if A is the notation for Wed->Thu and B is the notation for Thu->Fri, they would write it as BA or B⋅A. It may seem backwards, but that's they way mathematicians roll.
If Alf and Betty went to visit Anna and Graham on a Wednesday and came home on a Friday, they'd need to figure out the permutation Wed->Fri from the permutations Wed->Thu and Thu->Fri. Mathematicians call this either composition or multiplication, and if A is the notation for Wed->Thu and B is the notation for Thu->Fri, they would write it as BA or B∙A. It may seem backwards, but that's they way mathematicians roll.


Note that B⋅A will NOT give the same result as A⋅B – unlike regular multiplication of numbers, this sort of multiplication is generally not commutative. (There is an exception to this rule; when two or more cycles are disjoint they can be performed in any order.)
Note that B∙A will NOT give the same result as A∙B – unlike regular multiplication of numbers, this sort of multiplication is generally not commutative. (There is an exception to this rule; when two or more cycles are disjoint they can be performed in any order.)


The cycle notation for Thu->Fri is
The cycle notation for Thu->Fri is
Line 79: Line 79:
Thu->Fri: (1 10 4 13 2 8 9 11 3 6) (5 7) (12 14)
Thu->Fri: (1 10 4 13 2 8 9 11 3 6) (5 7) (12 14)


and the multiplication Thu->Fri⋅Wed->Thu gives the result
and the multiplication Thu->Fri∙Wed->Thu gives the result


Wed->Fri: (1 10 15 7 6 ) (2 9 14 13 11 4 8 5 12)
Wed->Fri: (1 10 15 7 6 ) (2 9 14 13 11 4 8 5 12)
Line 101: Line 101:
Their choice of orderings for cycle notation (i.e. smallest number first for cycles, cycles sorted in ascending order by first number) is not mandated. If your solution uses a different ordering, describe it.
Their choice of orderings for cycle notation (i.e. smallest number first for cycles, cycles sorted in ascending order by first number) is not mandated. If your solution uses a different ordering, describe it.


Similarly, right-to-left evaluation of cycle multiplication as composition of functions is not mandated. Show how Thu->Fri⋅Wed->Thu would be written in your solution.
Similarly, right-to-left evaluation of cycle multiplication as composition of functions is not mandated. Show how Thu->Fri∙Wed->Thu would be written in your solution.


Alf and Betty's system is one-based. If a zero-based system is more appropriate, then use that, but provide the means (e.g. one or more functions, procedures, subroutines, methods, or words, et cetera) to allow conversion to and from zero-based and one-based representations so that user I/O can be one-based. State if this is the case in your solution.
Alf and Betty's system is one-based. If a zero-based system is more appropriate, then use that, but provide the means (e.g. one or more functions, procedures, subroutines, methods, or words, et cetera) to allow conversion to and from zero-based and one-based representations so that user I/O can be one-based. State if this is the case in your solution.
Line 217: Line 217:
a, b and c are permutations in ZBCN. c is equal to applying first b
a, b and c are permutations in ZBCN. c is equal to applying first b
and then a to a string i.e. a.b)
and then a to a string i.e. a⋅b)
recompose ( a --> b );
recompose ( a --> b );
Retrieved from "https://rosettacode.org/wiki/Cycles_of_a_permutation"