vascosch92 / symmetria Goto Github PK

As the title says.

This will improve the documentation.

Moreover:

• correct all the wrong snippet of code
• add a GitHub actions to check that the snippet of code are always working
• can we do that also for the documentation and for the README ?
• add entry in the Makefile to make it easy testing that locally

Reference: https://docs.python.org/3/library/doctest.html

Implement a method which returns True if two permutations commute. False otheriwise.

Proposed API

def commute(self, other) -> bool

Ref: https://math.stackexchange.com/questions/440568/are-there-any-conditions-such-that-2-permutations-in-s-4-are-commutative

Add a method that returns if two permutations are conjugate.

Two permutations $\sigma, \tau \in S_n$ are conjugate if there is $\delta \in S_n$ such that $\delta \sigma \delta^{-1} = \tau$.
Note that two permutations are conjugate if and only if they have the same cycle type. Therefore, this issue is dependent from #6

Possible API

>>> Permutation(1, 2, 3).is_conjugate(Permutation(2, 1, 3))
False

For instance, when we want to compute the sign of an Permutation object, we convert it to a CycleDecomposition and then
we compute the sign.

Perhaps is better to compute the sign directly by counting the number of inversions, i.e., using the base definition of sign.

To implement that we need #25 .

Just as the title says :-)

Rework meta tests to change the order of the methods like the following:

• the init
• all the magic methods in alphabetical order
• all the others methods in alphabetical order

The old order was not so intuitive, and in this way we respect the order of the docs.

Add method .describe() to all the subclasses of _Element.

The method return a string representing a table with all the important information about the element.

Should we insert the method in _Element, or every class should have a different .describe() method?

Given the Lehman code and the order of the symmetric group return the relative permutation.

@classmethod
def from_lehman_code(code: int, n: int) -> "Permutation"
    ...

Update the following:

• README.md with link to documentation
• pyproject.toml with link to documentation
• Refactor README.md

Add a PR Template

The package should have a more complet CLI than the one now present.

We should be able to give a permutation/cycle/cycle decomposition in a particular notation (TBD) and to retrieve information about it.

For example

symmetria (1, 2, 3) --order

and it will print the order of the permutation (1, 2, 3)

Similar

symmetria (1 2)(3 4)(5 6 8 7) --order

will print the order of the cycle decomposition (1 2)(3 4)(5 6 8 7)

We plan to add a lot of methods for the classes: Permutation, Cycle and CycleDecomposition. This means that the classes will grow in complexity. To make it easier for developer to work with them we should implement tests to check that the methods follow the same order in every class.

Order proposed:

• __init__
• Magic methods in alphabetical order
• properties in alphabetic order
• All others methods in alphabetical order

The tests should ideally be in test_meta.test_order

Implement a method for the classes Permutation and CycleDecomposition which returns the Lehmer code.

Proposed API:

def lehmer_code(self) -> int:
    ...

Reference: https://en.wikipedia.org/wiki/Lehmer_code#:~:text=In%20mathematics%20and%20in%20particular,example%20of%20an%20inversion%20table.

Recall that a record of a permutation $\sigma$ is an element i such that $\sigma$(j) < $\sigma$(i) for all j < i.

Add issue templates.

Add a method .map(), which return a dictionary describing the map defined by an element.

Expose this method in the class _ELEMENT.

Investigate@classmethod and eventually make every constructor a @classmethod.

Implement a method to check if a permutation is regular.

Recall that a permutation :math:\sigma is regular if either has no fixed-points and it is the product of disjoint cycles of the same length or it is the identity.

Proposed API

def is_regular(self) -> bool:
    ...

As the title, there are docstrings with missing examples.

Complete it :-)

Introduce the magic method __pow__ for all the subclasses of _Element.

The power of a permutation can be defined just for integer (positive and negative).

To define a negative power of a permutation, we need to be able to compute its inverse. See issue #4 .

Note that a $\sigma^0=\sigma$ for every permutation $\sigma$ in $S_n$ and every $n \in \mathbb{N}$

Implement the following:

• #70
• #74
• #76
• Implement weak_exceedances method (completed in #77 )
• #81

All the methods should return the a list of indices with the relative elements.

Complete documentation for release 0.0.1

Add the method sgn (sign) to the classes Permutation, Cycle and CycleDecomposition.

Fact: the sign of a cycle is -1 if the cycle has even length.

Include a reference of the above fact in the PR.

Implement the algorithm which creates all the permutations of a given degree using the lexicographic ordering.

Implement a method which returns the lexicographic order of a permutation

Create a module which perform benchmarking.

Add a method .inverse() which return the inverse of a given permutation, i.e., for a given permutation $\tau \in S_n$ find the only permutation $\sigma \in S_n$ such that $\sigma * \tau = \tau * \sigma = id$.

The method should be exposed in the class _Element.

Implement a method which return a list of 2-tuple which represents the indices of the inversions in the permutation.

Recall that an inversion of a permutation $\sigma$ is a pair (i, j) of positions where the entries of a permutation are in the opposite order: i<j and $\sigma$(i) > $\sigma$(j).

An ascent of a permutation $\sigma$ of n is any position i < n where the following value is bigger than the current one.

Checklist:

• Automate testing
• Automate formatting and linting
• Check PR title workflow
• Automatic release/publish of package
• Automatic release/publish of docs
• Automatic DOCS testing

Add a method to compute the cycle type of a given permutation.

The cycle type of a permutation is defined here.

Open questions:

• should the method return a list or a tuple?

implement exceedances method.

An exceedance of a permutation $\sigma$ is an index j such that $\sigma(j)$ > j. If the inequality is not strict, then j is called a weak exceedance.

A a descent is the inverse of an ascent.

implement a method to compute the descents of a given permutation

Implement generation of permutations using the Steinhaus–Johnson–Trotter algorithm.

In particular, explain how the one-line notation is made.

Develop the structure for the new module to generate permutation, and update the documentation.

The degree of a permutation is the number of elements in the set. This is actually the length of the permutation.
Therefore, this should be the implementation

def degree(self) -> int:
# docstring
    return len(self)

Implement Heap algorithm to generate permutations

Implement the infrastructure to generate random permutation following a given algorithm.

Proposed API

import symmetria

random_permutations = symmetria.random(algorithm="entry-by-entry", degree=3)

for permutation in random_permutations:
   permutation

The first step is:

• #108

It follows a list of algorithm of permutations we want to implement:

• Entry-by-entry
• Fisher-Yates shuffles
• Sattolo
• Sorting method

Reference:

• https://en.wikipedia.org/wiki/Random_permutation
• https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Implement the infrastructure to generate permutation following a specific algorithm.

Proposed API

from symmetria import generate
...
for permutation in generate(algorithm="lexicographic", degree=4):
    print(permutation)

The first step is:

• #88

It follows a list of algorithm of permutations we want to implement:

• #90
• #105
• #97
• #94
• Ehrlich's star-transposition algorithm;
• #106
• Sawada-Williams' algorithm;
• Corbett's algorithm;
• Single-track ordering;
• Single-track Gray code;
• Nested swaps generating algorithm;

Reference: https://en.wikipedia.org/wiki/Permutation#Numbering_permutations

Develop a workflow which is triggered when a new release is published.

The workflow should check that the version number in pyproject.toml, the one in the __init__,py and the tag for the release are the same.

Document the canonical cycle notation that the package use for both classes: Cycle and CycleDecomposition

Checklist:

• Add to pre-commit checks for toml
• Add to pre-commit checks for pytest tests names

Change the imports in the test module to respect the IPA.

In this way, if a change break the API, we can know from the tests.

The templates for the issues seem not to work properly.

Change from .md to .yaml as describe in the GitHub documentation.

Add methods is_even and is_odd for permutations.

Recall that a permutation is said to be even if it is the product of an even number of transpositions. Otherwise, it is said odd.

This issue is dependent from issue #9