Efficient Disjoint Cycle Calculation | Past Exam Paper Help

  • Thread starter Charles007
  • Start date
  • Tags
    Exam Paper
In summary, to express a permutation as the product of disjoint cycles, you can calculate from right to left by starting with the rightmost element and finding its image under each cycle, then repeating this process for each subsequent element in the permutation. This method does not require converting the permutation into 2-row notation.
  • #1
Charles007
22
0
Express as the product of disjoint cycles:
a. (1,2,3)(4,5)(1,6,7,8,9)(1,5)
b. (1,2)(1,2,3)(1,2)


I know how to do in 2 row permutations, with right to - left. can anyone tell me , how to express it without transfer it into 2 row permutations.

2 disjoint product. eg. (123)(234) calculate from right to left. how ?

I know transfer it into 2 row permutations, (1-2,2-3,3-1,4-4)* (1-1,2-3,3-4,4-2)



Thank you. I am doing my past exam paper, university doesn't give us answer.
 
Physics news on Phys.org
  • #2
Welcome to PF!

Hi Charles007! Welcome to PF! :wink:
Charles007 said:
2 disjoint product. eg. (123)(234) calculate from right to left. how ?

The right one sends 2 to 3, then left one sends 3 to 1, so both together send 2 to 1.

Then do the same, starting with 3, and again starting with 4, and again starting with 1. :smile:

(I've done them in the order 2,3,4,1, but any order would do)
 
  • #3


I am familiar with efficient methods for calculating disjoint cycles. In order to express the given content as a product of disjoint cycles, we simply need to group the elements that are in each cycle together and write them in the form of (a,b,c,...), where a, b, c, etc. represent the elements in the cycle.

a. (1,2,3)(4,5)(1,6,7,8,9)(1,5) can be expressed as (1,2,3)(4,5)(6,7,8,9). This means that element 1 maps to 2, 2 maps to 3, 3 maps to 1, 4 maps to 5, 6 maps to 7, 7 maps to 8, 8 maps to 9, and 9 maps to 6. The cycle (1,5) does not need to be included since it is already covered in the first cycle.

b. (1,2)(1,2,3)(1,2) can be expressed as (1,2,3). This means that element 1 maps to 2, 2 maps to 3, and 3 maps to 1. The cycle (1,2) is not needed since it is already covered in the third cycle.

To calculate the product of disjoint cycles, we start from the right and work our way to the left. For example, in the first cycle (1,2,3), we start with 3 and find the element that maps to it, which is 1. Then we move to 1 and find the element that maps to it, which is 2. Finally, we move to 2 and find the element that maps to it, which is 3. This completes the first cycle. We then move on to the next cycle and repeat the process until we have gone through all the cycles.

I hope this helps with your past exam paper. Good luck!
 

What is efficient disjoint cycle calculation?

Efficient disjoint cycle calculation refers to a mathematical algorithm used to find the disjoint cycles in a given permutation. It is commonly used in the field of graph theory and has applications in various areas such as network analysis, cryptography, and computer science.

How does the algorithm for efficient disjoint cycle calculation work?

The algorithm for efficient disjoint cycle calculation involves breaking down a permutation into its individual cycles and then identifying the disjoint cycles among them. This is done by starting with any element in the permutation and tracing its cycle until it reaches back to the starting element. This process is repeated until all cycles have been identified and any overlapping cycles are merged to create disjoint cycles.

What are the advantages of using efficient disjoint cycle calculation?

Efficient disjoint cycle calculation has several advantages, including its ability to quickly identify disjoint cycles in large permutations, its efficiency in identifying overlapping cycles, and its applicability in various fields. It can also be easily implemented in computer programs, making it a useful tool for data analysis and problem-solving.

Are there any limitations to efficient disjoint cycle calculation?

While efficient disjoint cycle calculation is a useful algorithm, it does have limitations. One limitation is that it can only be applied to permutations, which may not be applicable in all scenarios. Additionally, in some cases, the algorithm may not be able to identify all disjoint cycles, leading to potential errors in the results.

Can efficient disjoint cycle calculation be used for other purposes besides graph theory?

Yes, efficient disjoint cycle calculation can be applied in various fields besides graph theory. It has applications in cryptography for generating and analyzing secret keys, in computer science for analyzing algorithms and data structures, and in network analysis for identifying patterns and relationships in large datasets.

Similar threads

Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
9K
  • Calculus and Beyond Homework Help
Replies
4
Views
6K
  • General Math
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
10K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
8K
Back
Top