partitionstability

Implementation of Algorithms 1 and 4 of [Ball2018]

partitionstability.geq(P, Q)

Test if P is coarser than or equal to Q. Both, equality and coarseness are up to label isomorphism, i.e. partitions [0, 0, 1] and [3, 3, 7] are equal. A partition P is coarser than a partition Q if each cluster in Q is a subset of a cluster in P.

Data representation is:

• Partition P: array-like, i.e. P[i] corresponds to the (arbitrary) cluster id of node i

Usage:

>>> from partitionstability import geq
>>> P = [0,0,0,1,1,1]
>>> P_prime = [1,1,1,0,0,0]
>>> Q = [3,3,0,2,2,1]
>>> R = [3,3,3,3,1,1]
>>> assert geq(P, Q) == True
>>> assert geq(P, P_prime) == True
>>> assert geq(P, P_prime) == geq(P_prime, P)  # Cluster ids are arbitrary!
>>> assert geq(P, R) == False
>>> assert geq(R, P) == False
>>> S = list(range(100))
>>> from random import shuffle
>>> shuffle(S)
>>> assert geq(list(range(100)), S) == True

Parameters:

• P (list | tuple) – A partition in an array-like representation of node ids
• Q (list | tuple) – A partition in an array-like representation of node ids

Returns:

True, if \(P \geq Q\)

Return type:

bool

partitionstability.test_stability(P, S)

Test partition stability.

Usage:

>>> from sparsepermutation import SparsePermutation
>>> from partitionstability import test_stability
>>> p1 = SparsePermutation([1, 0, 2, 3, 5, 4, 6, 7, 8, 9])  # (0 1)(4 5)
>>> p2 = SparsePermutation([0, 1, 2, 3, 4, 5, 6, 7, 9, 8])  # (8 9)
>>> p3 = SparsePermutation([0, 8, 2, 3, 4, 5, 6, 7, 1, 9])  # (1 8)
>>> S = [p1, p2, p3]
>>> P = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> assert test_stability(P, S) == True
>>> Q = [1, 1, 0, 0, 0, 0, 0, 0, 2, 2]
>>> assert test_stability(Q, S) == False

Parameters:

• P (list | tuple) – A partition in an array-like representation, clusters are identified by cluster ids
• S (list | tuple | set) – A set of generators for a permutation group

Returns:

True, if the partition is stable

Return type:

bool

orbits

Implementation of Algorithms 2 and 3 of [Ball2018]

orbits.compute_orbit_partition(S, n)

Algorithm to compute the partition of orbits from a set of generators of the permutation group.

Data representations are: * Permutation pi: array-like, i.e. pi[i] corresponds to \(i \mapsto i^\pi\), which MUST be hashable * Set of generators S: any container that is iterable repeatedly (e.g. list or set) * Partition O: array-like, i.e. O[i] corresponds to the (arbitrary) cluster id of node i

Besides the arbitrariness of cluster ids, this algorithm guarantees that O[i] == i if i is the smallest node id/label that is part of this cluster.

Worst case time complexity is \(O(|S|\cdot n)\).

Usage:

>>> from sparsepermutation import SparsePermutation
>>> from orbits import compute_orbit_partition
>>> p1 = SparsePermutation([1, 0, 2, 3, 5, 4, 6, 7, 8, 9])  # (0 1)(4 5)
>>> p2 = SparsePermutation([0, 1, 2, 3, 4, 5, 6, 7, 9, 8])  # (8 9)
>>> p3 = SparsePermutation([0, 8, 2, 3, 4, 5, 6, 7, 1, 9])  # (1 8)
>>> orbits = compute_orbit_partition([p1, p2, p3], 10)
>>> assert orbits == [0, 0, 2, 3, 4, 4, 6, 7, 0, 0]

Parameters:

• S (list | set | tuple) – A bunch of generators for a permutation group
• n (int) – The length of the set of elements the generated group acts on

Returns:

The partition of orbits of the permutation group

Return type:

list

sparsepermutation

Simple implementation of a sparse permutation datastructure which is more efficient than saving permutation lists of length n each.

class sparsepermutation.SparsePermutation(permutation_array)

Bases: object

A minimal implementation of a sparse permutation that partly mimics the Permutation implementation of sympy.combinatorics.Permutation.

Usage:

>>> from sparsepermutation import SparsePermutation
>>> p = [0, 1, 3, 2]  # Permutation (2 3)
>>> sp = SparsePermutation(p)  # Sparsify
>>> q = list(sp)  # Convert back to list
>>> assert p == q

atoms()

Returns:The set of elements Return type:set

length()

Returns:The number of affected elements Return type:int

size

Returns:The number of elements the permutation acts on Return type:int

support()

Returns:The list of affected elements Return type:list