CODEWITHSUNDEEP
pythoncircular-permutations
twister
twister

Reputation: 3

Composition of cycle permutation

What is a good Python program to calculate the composition( from right to left) of cycle permutations? I know how to calculate the answer, but I don't know the algorithm for a Python program.
For example; '(1,6,5,3)(1,4,2,3)' has the solution '(1,4,2)(3,6,5)'. Because 1 - 4 - 4, 4 - 2 - 2, 2 - 3 - 1 and 3 - 1 - 6, 6 - 6 - 5, 5 - 5 - 3
On the internet I couldn't find where to begin or what to do. Can someone please help me?

Upvotes: 0

Views: 1092

Answers (1)

grey_ranger
grey_ranger

Reputation: 1030

The Sympy package handles cycle permutations nicely. Your method of writing permutations is called "Disjoint Cycle Notation". Here's an example using your cycles:

from sympy.combinatorics.permutations import Permutation

a = Permutation([[1, 6, 5, 3]])  
b = Permutation([[1, 4, 2, 3]])

new_perm = b * a

This gives output (142)(365) for new_perm.

For any of these cycles, you can call them like a function. For example, we can input 1 to new_perm and would expect 4 as an output:

> new_perm(1)
4

Edit

The Sympy permutations can be used as the building blocks for a function which composes cycle permutations together. The original question asked for a string input and output. Here is one example (you may have to modify based on your string input):

import re
import functools

def compose_cycles(input_string):
    # Split the cycles by regex
    cycles = re.findall("\(([\d,]+)\)", input_string)

    # Break each cycle into a list of integers
    cycles = [list(map(int, x.split(","))) for x in cycles]

    # Make each cycle into a Sympy Permutation
    cycles = [Permutation([x]) for x in cycles]

    composition = functools.reduce(lambda x, y: y * x, cycles)

    return str(composition)

compose_cycles('(1,6,5,3)(1,4,2,3)')

The last line of the functions calls str which returns the string representation (not the original permutation). Our output is '(1 4 2)(3 6 5)'

Upvotes: 0

Related Questions