modelparameters.sympy.combinatorics package

Submodules

modelparameters.sympy.combinatorics.fp_groups module

Finitely Presented Groups and its algorithms.

modelparameters.sympy.combinatorics.fp_groups.fp_group(fr_grp, relators=[])

modelparameters.sympy.combinatorics.fp_groups.vfp_group(fr_grpm, relators)

modelparameters.sympy.combinatorics.fp_groups.xfp_group(fr_grp, relators=[])

modelparameters.sympy.combinatorics.free_groups module

modelparameters.sympy.combinatorics.free_groups.free_group(symbols)

Construct a free group returning (FreeGroup, (f_0, f_1, ..., f_(n-1)).

Parameters:

symbols (str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)) –

Examples

>>> from .free_groups import free_group
>>> F, x, y, z = free_group("x, y, z")
>>> F
<free group on the generators (x, y, z)>
>>> x**2*y**-1
x**2*y**-1
>>> type(_)
<class 'sympy.combinatorics.free_groups.FreeGroupElement'>

modelparameters.sympy.combinatorics.free_groups.vfree_group(symbols)

Construct a free group and inject f_0, f_1, ..., f_(n-1) as symbols into the global namespace.

Parameters:

symbols (str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)) –

Examples

>>> from .free_groups import vfree_group
>>> vfree_group("x, y, z")
<free group on the generators (x, y, z)>
>>> x**2*y**-2*z
x**2*y**-2*z
>>> type(_)
<class 'sympy.combinatorics.free_groups.FreeGroupElement'>

modelparameters.sympy.combinatorics.free_groups.xfree_group(symbols)

Construct a free group returning (FreeGroup, (f_0, f_1, ..., f_(n-1))).

Parameters:

symbols (str, Symbol/Expr or sequence of str, Symbol/Expr (may be empty)) –

Examples

>>> from .free_groups import xfree_group
>>> F, (x, y, z) = xfree_group("x, y, z")
>>> F
<free group on the generators (x, y, z)>
>>> y**2*x**-2*z**-1
y**2*x**-2*z**-1
>>> type(_)
<class 'sympy.combinatorics.free_groups.FreeGroupElement'>

modelparameters.sympy.combinatorics.generators module

modelparameters.sympy.combinatorics.generators.alternating(n)

Generates the alternating group of order n, An.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = True
>>> from .generators import alternating
>>> list(alternating(3))
[(2), (0 1 2), (0 2 1)]

modelparameters.sympy.combinatorics.generators.cyclic(n)

Generates the cyclic group of order n, Cn.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = True
>>> from .generators import cyclic
>>> list(cyclic(5))
[(4), (0 1 2 3 4), (0 2 4 1 3),
 (0 3 1 4 2), (0 4 3 2 1)]

See also

dihedral

modelparameters.sympy.combinatorics.generators.dihedral(n)

Generates the dihedral group of order 2n, Dn.

The result is given as a subgroup of Sn, except for the special cases n=1 (the group S2) and n=2 (the Klein 4-group) where that’s not possible and embeddings in S2 and S4 respectively are given.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = True
>>> from .generators import dihedral
>>> list(dihedral(3))
[(2), (0 2), (0 1 2), (1 2), (0 2 1), (2)(0 1)]

See also

cyclic

modelparameters.sympy.combinatorics.generators.rubik(n)

Return permutations for an nxn Rubik’s cube.

Permutations returned are for rotation of each of the slice from the face up to the last face for each of the 3 sides (in this order): front, right and bottom. Hence, the first n - 1 permutations are for the slices from the front.

modelparameters.sympy.combinatorics.generators.rubik_cube_generators()

Return the permutations of the 3x3 Rubik’s cube, see http://www.gap-system.org/Doc/Examples/rubik.html

modelparameters.sympy.combinatorics.generators.symmetric(n)

Generates the symmetric group of order n, Sn.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = True
>>> from .generators import symmetric
>>> list(symmetric(3))
[(2), (1 2), (2)(0 1), (0 1 2), (0 2 1), (0 2)]

modelparameters.sympy.combinatorics.graycode module

class modelparameters.sympy.combinatorics.graycode.GrayCode(n, *args, **kw_args)

Bases: Basic

A Gray code is essentially a Hamiltonian walk on a n-dimensional cube with edge length of one. The vertices of the cube are represented by vectors whose values are binary. The Hamilton walk visits each vertex exactly once. The Gray code for a 3d cube is [‘000’,’100’,’110’,’010’,’011’,’111’,’101’, ‘001’].

A Gray code solves the problem of sequentially generating all possible subsets of n objects in such a way that each subset is obtained from the previous one by either deleting or adding a single object. In the above example, 1 indicates that the object is present, and 0 indicates that its absent.

Gray codes have applications in statistics as well when we want to compute various statistics related to subsets in an efficient manner.

References: [1] Nijenhuis,A. and Wilf,H.S.(1978). Combinatorial Algorithms. Academic Press. [2] Knuth, D. (2011). The Art of Computer Programming, Vol 4 Addison Wesley

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3)
>>> list(a.generate_gray())
['000', '001', '011', '010', '110', '111', '101', '100']
>>> a = GrayCode(4)
>>> list(a.generate_gray())
['0000', '0001', '0011', '0010', '0110', '0111', '0101', '0100',     '1100', '1101', '1111', '1110', '1010', '1011', '1001', '1000']

property current

Returns the currently referenced Gray code as a bit string.

Examples

>>> from .graycode import GrayCode
>>> GrayCode(3, start='100').current
'100'

default_assumptions = {}

generate_gray(**hints)

Generates the sequence of bit vectors of a Gray Code.

[1] Knuth, D. (2011). The Art of Computer Programming, Vol 4, Addison Wesley

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3)
>>> list(a.generate_gray())
['000', '001', '011', '010', '110', '111', '101', '100']
>>> list(a.generate_gray(start='011'))
['011', '010', '110', '111', '101', '100']
>>> list(a.generate_gray(rank=4))
['110', '111', '101', '100']

See also

skip

property n

Returns the dimension of the Gray code.

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(5)
>>> a.n
5

next(delta=1)

Returns the Gray code a distance delta (default = 1) from the current value in canonical order.

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3, start='110')
>>> a.next().current
'111'
>>> a.next(-1).current
'010'

property rank

Ranks the Gray code.

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects w.r.t. a given order. For example, the 4 bit binary reflected Gray code (BRGC) ‘0101’ has a rank of 6 as it appears in the 6th position in the canonical ordering of the family of 4 bit Gray codes.

References: [1] http://statweb.stanford.edu/~susan/courses/s208/node12.html

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3)
>>> list(a.generate_gray())
['000', '001', '011', '010', '110', '111', '101', '100']
>>> GrayCode(3, start='100').rank
7
>>> GrayCode(3, rank=7).current
'100'

See also

unrank

property selections

Returns the number of bit vectors in the Gray code.

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3)
>>> a.selections
8

skip()

Skips the bit generation.

Examples

>>> from .graycode import GrayCode
>>> a = GrayCode(3)
>>> for i in a.generate_gray():
...     if i == '010':
...         a.skip()
...     print(i)
...
000
001
011
010
111
101
100

See also

generate_gray

classmethod unrank(n, rank)

Unranks an n-bit sized Gray code of rank k. This method exists so that a derivative GrayCode class can define its own code of a given rank.

The string here is generated in reverse order to allow for tail-call optimization.

Examples

>>> from .graycode import GrayCode
>>> GrayCode(5, rank=3).current
'00010'
>>> GrayCode.unrank(5, 3)
'00010'

See also

rank

modelparameters.sympy.combinatorics.graycode.bin_to_gray(bin_list)

Convert from binary coding to gray coding.

We assume big endian encoding.

Examples

>>> from .graycode import bin_to_gray
>>> bin_to_gray('111')
'100'

See also

gray_to_bin

modelparameters.sympy.combinatorics.graycode.get_subset_from_bitstring(super_set, bitstring)

Gets the subset defined by the bitstring.

Examples

>>> from .graycode import get_subset_from_bitstring
>>> get_subset_from_bitstring(['a', 'b', 'c', 'd'], '0011')
['c', 'd']
>>> get_subset_from_bitstring(['c', 'a', 'c', 'c'], '1100')
['c', 'a']

See also

graycode_subsets

modelparameters.sympy.combinatorics.graycode.gray_to_bin(bin_list)

Convert from Gray coding to binary coding.

We assume big endian encoding.

Examples

>>> from .graycode import gray_to_bin
>>> gray_to_bin('100')
'111'

See also

bin_to_gray

modelparameters.sympy.combinatorics.graycode.graycode_subsets(gray_code_set)

Generates the subsets as enumerated by a Gray code.

Examples

>>> from .graycode import graycode_subsets
>>> list(graycode_subsets(['a', 'b', 'c']))
[[], ['c'], ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'],     ['a', 'c'], ['a']]
>>> list(graycode_subsets(['a', 'b', 'c', 'c']))
[[], ['c'], ['c', 'c'], ['c'], ['b', 'c'], ['b', 'c', 'c'],     ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'c'],     ['a', 'b', 'c'], ['a', 'c'], ['a', 'c', 'c'], ['a', 'c'], ['a']]

See also

get_subset_from_bitstring

modelparameters.sympy.combinatorics.graycode.random_bitstring(n)

Generates a random bitlist of length n.

Examples

>>> from .graycode import random_bitstring
>>> random_bitstring(3) 
100

modelparameters.sympy.combinatorics.group_constructs module

modelparameters.sympy.combinatorics.group_constructs.DirectProduct(*groups)

Returns the direct product of several groups as a permutation group.

This is implemented much like the __mul__ procedure for taking the direct product of two permutation groups, but the idea of shifting the generators is realized in the case of an arbitrary number of groups. A call to DirectProduct(G1, G2, …, Gn) is generally expected to be faster than a call to G1*G2*…*Gn (and thus the need for this algorithm).

Examples

>>> from .group_constructs import DirectProduct
>>> from .named_groups import CyclicGroup
>>> C = CyclicGroup(4)
>>> G = DirectProduct(C, C, C)
>>> G.order()
64

See also

__mul__

modelparameters.sympy.combinatorics.named_groups module

modelparameters.sympy.combinatorics.named_groups.AbelianGroup(*cyclic_orders)

Returns the direct product of cyclic groups with the given orders.

According to the structure theorem for finite abelian groups ([1]), every finite abelian group can be written as the direct product of finitely many cyclic groups.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .named_groups import AbelianGroup
>>> AbelianGroup(3, 4)
PermutationGroup([
        (6)(0 1 2),
        (3 4 5 6)])
>>> _.is_group
True

See also

DirectProduct

References

[1] http://groupprops.subwiki.org/wiki/Structure_theorem_for_finitely_generated_abelian_groups

modelparameters.sympy.combinatorics.named_groups.AlternatingGroup(n)

Generates the alternating group on n elements as a permutation group.

For n > 2, the generators taken are (0 1 2), (0 1 2 ... n-1) for n odd and (0 1 2), (1 2 ... n-1) for n even (See [1], p.31, ex.6.9.). After the group is generated, some of its basic properties are set. The cases n = 1, 2 are handled separately.

Examples

>>> from .named_groups import AlternatingGroup
>>> G = AlternatingGroup(4)
>>> G.is_group
True
>>> a = list(G.generate_dimino())
>>> len(a)
12
>>> all(perm.is_even for perm in a)
True

See also

SymmetricGroup, CyclicGroup, DihedralGroup

References

[1] Armstrong, M. “Groups and Symmetry”

modelparameters.sympy.combinatorics.named_groups.CyclicGroup(n)

Generates the cyclic group of order n as a permutation group.

The generator taken is the n-cycle (0 1 2 ... n-1) (in cycle notation). After the group is generated, some of its basic properties are set.

Examples

>>> from .named_groups import CyclicGroup
>>> G = CyclicGroup(6)
>>> G.is_group
True
>>> G.order()
6
>>> list(G.generate_schreier_sims(af=True))
[[0, 1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 0], [2, 3, 4, 5, 0, 1],
[3, 4, 5, 0, 1, 2], [4, 5, 0, 1, 2, 3], [5, 0, 1, 2, 3, 4]]

See also

SymmetricGroup, DihedralGroup, AlternatingGroup

modelparameters.sympy.combinatorics.named_groups.DihedralGroup(n)

Generates the dihedral group D_n as a permutation group.

The dihedral group D_n is the group of symmetries of the regular n-gon. The generators taken are the n-cycle a = (0 1 2 ... n-1) (a rotation of the n-gon) and b = (0 n-1)(1 n-2)... (a reflection of the n-gon) in cycle rotation. It is easy to see that these satisfy a**n = b**2 = 1 and bab = ~a so they indeed generate D_n (See [1]). After the group is generated, some of its basic properties are set.

Examples

>>> from .named_groups import DihedralGroup
>>> G = DihedralGroup(5)
>>> G.is_group
True
>>> a = list(G.generate_dimino())
>>> [perm.cyclic_form for perm in a]
[[], [[0, 1, 2, 3, 4]], [[0, 2, 4, 1, 3]],
[[0, 3, 1, 4, 2]], [[0, 4, 3, 2, 1]], [[0, 4], [1, 3]],
[[1, 4], [2, 3]], [[0, 1], [2, 4]], [[0, 2], [3, 4]],
[[0, 3], [1, 2]]]

See also

SymmetricGroup, CyclicGroup, AlternatingGroup

References

[1] http://en.wikipedia.org/wiki/Dihedral_group

modelparameters.sympy.combinatorics.named_groups.RubikGroup(n)

Return a group of Rubik’s cube generators

>>> from .named_groups import RubikGroup
>>> RubikGroup(2).is_group
True

modelparameters.sympy.combinatorics.named_groups.SymmetricGroup(n)

Generates the symmetric group on n elements as a permutation group.

The generators taken are the n-cycle (0 1 2 ... n-1) and the transposition (0 1) (in cycle notation). (See [1]). After the group is generated, some of its basic properties are set.

Examples

>>> from .named_groups import SymmetricGroup
>>> G = SymmetricGroup(4)
>>> G.is_group
True
>>> G.order()
24
>>> list(G.generate_schreier_sims(af=True))
[[0, 1, 2, 3], [1, 2, 3, 0], [2, 3, 0, 1], [3, 1, 2, 0], [0, 2, 3, 1],
[1, 3, 0, 2], [2, 0, 1, 3], [3, 2, 0, 1], [0, 3, 1, 2], [1, 0, 2, 3],
[2, 1, 3, 0], [3, 0, 1, 2], [0, 1, 3, 2], [1, 2, 0, 3], [2, 3, 1, 0],
[3, 1, 0, 2], [0, 2, 1, 3], [1, 3, 2, 0], [2, 0, 3, 1], [3, 2, 1, 0],
[0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3], [3, 0, 2, 1]]

See also

CyclicGroup, DihedralGroup, AlternatingGroup

References

[1] http://en.wikipedia.org/wiki/Symmetric_group#Generators_and_relations

modelparameters.sympy.combinatorics.partitions module

class modelparameters.sympy.combinatorics.partitions.IntegerPartition(partition, integer=None)

Bases: Basic

This class represents an integer partition.

In number theory and combinatorics, a partition of a positive integer, n, also called an integer partition, is a way of writing n as a list of positive integers that sum to n. Two partitions that differ only in the order of summands are considered to be the same partition; if order matters then the partitions are referred to as compositions. For example, 4 has five partitions: [4], [3, 1], [2, 2], [2, 1, 1], and [1, 1, 1, 1]; the compositions [1, 2, 1] and [1, 1, 2] are the same as partition [2, 1, 1].

See also

sympy.utilities.iterables.partitions, sympy.utilities.iterables.multiset_partitions

Reference

http://en.wikipedia.org/wiki/Partition_%28number_theory%29

as_dict()

Return the partition as a dictionary whose keys are the partition integers and the values are the multiplicity of that integer.

Examples

>>> from .partitions import IntegerPartition
>>> IntegerPartition([1]*3 + [2] + [3]*4).as_dict()
{1: 3, 2: 1, 3: 4}

as_ferrers(char='#')

Prints the ferrer diagram of a partition.

Examples

>>> from .partitions import IntegerPartition
>>> print(IntegerPartition([1, 1, 5]).as_ferrers())
#####
#
#

property conjugate

Computes the conjugate partition of itself.

Examples

>>> from .partitions import IntegerPartition
>>> a = IntegerPartition([6, 3, 3, 2, 1])
>>> a.conjugate
[5, 4, 3, 1, 1, 1]

default_assumptions = {}

next_lex()

Return the next partition of the integer, n, in lexical order, wrapping around to [n] if the partition is [1, …, 1].

Examples

>>> from .partitions import IntegerPartition
>>> p = IntegerPartition([3, 1])
>>> print(p.next_lex())
[4]
>>> p.partition < p.next_lex().partition
True

prev_lex()

Return the previous partition of the integer, n, in lexical order, wrapping around to [1, …, 1] if the partition is [n].

Examples

>>> from .partitions import IntegerPartition
>>> p = IntegerPartition([4])
>>> print(p.prev_lex())
[3, 1]
>>> p.partition > p.prev_lex().partition
True

class modelparameters.sympy.combinatorics.partitions.Partition(*partition)

Bases: FiniteSet

This class represents an abstract partition.

A partition is a set of disjoint sets whose union equals a given set.

See also

sympy.utilities.iterables.partitions, sympy.utilities.iterables.multiset_partitions

property RGS

Returns the “restricted growth string” of the partition.

The RGS is returned as a list of indices, L, where L[i] indicates the block in which element i appears. For example, in a partition of 3 elements (a, b, c) into 2 blocks ([c], [a, b]) the RGS is [1, 1, 0]: “a” is in block 1, “b” is in block 1 and “c” is in block 0.

Examples

>>> from .partitions import Partition
>>> a = Partition([1, 2], [3], [4, 5])
>>> a.members
(1, 2, 3, 4, 5)
>>> a.RGS
(0, 0, 1, 2, 2)
>>> a + 1
{{3}, {4}, {5}, {1, 2}}
>>> _.RGS
(0, 0, 1, 2, 3)

default_assumptions = {}

classmethod from_rgs(rgs, elements)

Creates a set partition from a restricted growth string.

The indices given in rgs are assumed to be the index of the element as given in elements as provided (the elements are not sorted by this routine). Block numbering starts from 0. If any block was not referenced in rgs an error will be raised.

Examples

>>> from .partitions import Partition
>>> Partition.from_rgs([0, 1, 2, 0, 1], list('abcde'))
{{c}, {a, d}, {b, e}}
>>> Partition.from_rgs([0, 1, 2, 0, 1], list('cbead'))
{{e}, {a, c}, {b, d}}
>>> a = Partition([1, 4], [2], [3, 5])
>>> Partition.from_rgs(a.RGS, a.members)
{{2}, {1, 4}, {3, 5}}

property partition

Return partition as a sorted list of lists.

Examples

>>> from .partitions import Partition
>>> Partition([1], [2, 3]).partition
[[1], [2, 3]]

property rank

Gets the rank of a partition.

Examples

>>> from .partitions import Partition
>>> a = Partition([1, 2], [3], [4, 5])
>>> a.rank
13

sort_key(order=None)

Return a canonical key that can be used for sorting.

Ordering is based on the size and sorted elements of the partition and ties are broken with the rank.

Examples

>>> from ..utilities.iterables import default_sort_key
>>> from .partitions import Partition
>>> from ..abc import x
>>> a = Partition([1, 2])
>>> b = Partition([3, 4])
>>> c = Partition([1, x])
>>> d = Partition(list(range(4)))
>>> l = [d, b, a + 1, a, c]
>>> l.sort(key=default_sort_key); l
[{{1, 2}}, {{1}, {2}}, {{1, x}}, {{3, 4}}, {{0, 1, 2, 3}}]

modelparameters.sympy.combinatorics.partitions.RGS_enum(m)

RGS_enum computes the total number of restricted growth strings possible for a superset of size m.

Examples

>>> from .partitions import RGS_enum
>>> from .partitions import Partition
>>> RGS_enum(4)
15
>>> RGS_enum(5)
52
>>> RGS_enum(6)
203

We can check that the enumeration is correct by actually generating the partitions. Here, the 15 partitions of 4 items are generated:

>>> a = Partition(list(range(4)))
>>> s = set()
>>> for i in range(20):
...     s.add(a)
...     a += 1
...
>>> assert len(s) == 15

modelparameters.sympy.combinatorics.partitions.RGS_generalized(m)

Computes the m + 1 generalized unrestricted growth strings and returns them as rows in matrix.

Examples

>>> from .partitions import RGS_generalized
>>> RGS_generalized(6)
Matrix([
[  1,   1,   1,  1,  1, 1, 1],
[  1,   2,   3,  4,  5, 6, 0],
[  2,   5,  10, 17, 26, 0, 0],
[  5,  15,  37, 77,  0, 0, 0],
[ 15,  52, 151,  0,  0, 0, 0],
[ 52, 203,   0,  0,  0, 0, 0],
[203,   0,   0,  0,  0, 0, 0]])

modelparameters.sympy.combinatorics.partitions.RGS_rank(rgs)

Computes the rank of a restricted growth string.

Examples

>>> from .partitions import RGS_rank, RGS_unrank
>>> RGS_rank([0, 1, 2, 1, 3])
42
>>> RGS_rank(RGS_unrank(4, 7))
4

modelparameters.sympy.combinatorics.partitions.RGS_unrank(rank, m)

Gives the unranked restricted growth string for a given superset size.

Examples

>>> from .partitions import RGS_unrank
>>> RGS_unrank(14, 4)
[0, 1, 2, 3]
>>> RGS_unrank(0, 4)
[0, 0, 0, 0]

modelparameters.sympy.combinatorics.partitions.random_integer_partition(n, seed=None)

Generates a random integer partition summing to n as a list of reverse-sorted integers.

Examples

>>> from .partitions import random_integer_partition

For the following, a seed is given so a known value can be shown; in practice, the seed would not be given.

>>> random_integer_partition(100, seed=[1, 1, 12, 1, 2, 1, 85, 1])
[85, 12, 2, 1]
>>> random_integer_partition(10, seed=[1, 2, 3, 1, 5, 1])
[5, 3, 1, 1]
>>> random_integer_partition(1)
[1]

modelparameters.sympy.combinatorics.perm_groups module

modelparameters.sympy.combinatorics.perm_groups.PermGroup

alias of PermutationGroup

class modelparameters.sympy.combinatorics.perm_groups.PermutationGroup(*args, **kwargs)

Bases: Basic

The class defining a Permutation group.

PermutationGroup([p1, p2, …, pn]) returns the permutation group generated by the list of permutations. This group can be supplied to Polyhedron if one desires to decorate the elements to which the indices of the permutation refer.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .permutations import Cycle
>>> from .polyhedron import Polyhedron
>>> from .perm_groups import PermutationGroup

The permutations corresponding to motion of the front, right and bottom face of a 2x2 Rubik’s cube are defined:

>>> F = Permutation(2, 19, 21, 8)(3, 17, 20, 10)(4, 6, 7, 5)
>>> R = Permutation(1, 5, 21, 14)(3, 7, 23, 12)(8, 10, 11, 9)
>>> D = Permutation(6, 18, 14, 10)(7, 19, 15, 11)(20, 22, 23, 21)

These are passed as permutations to PermutationGroup:

>>> G = PermutationGroup(F, R, D)
>>> G.order()
3674160

The group can be supplied to a Polyhedron in order to track the objects being moved. An example involving the 2x2 Rubik’s cube is given there, but here is a simple demonstration:

>>> a = Permutation(2, 1)
>>> b = Permutation(1, 0)
>>> G = PermutationGroup(a, b)
>>> P = Polyhedron(list('ABC'), pgroup=G)
>>> P.corners
(A, B, C)
>>> P.rotate(0) # apply permutation 0
>>> P.corners
(A, C, B)
>>> P.reset()
>>> P.corners
(A, B, C)

Or one can make a permutation as a product of selected permutations and apply them to an iterable directly:

>>> P10 = G.make_perm([0, 1])
>>> P10('ABC')
['C', 'A', 'B']

See also

sympy.combinatorics.polyhedron.Polyhedron, sympy.combinatorics.permutations.Permutation

References

[1] Holt, D., Eick, B., O’Brien, E. “Handbook of Computational Group Theory”

[2] Seress, A. “Permutation Group Algorithms”

[3] http://en.wikipedia.org/wiki/Schreier_vector

[4] http://en.wikipedia.org/wiki/Nielsen_transformation #Product_replacement_algorithm

[5] Frank Celler, Charles R.Leedham-Green, Scott H.Murray, Alice C.Niemeyer, and E.A.O’Brien. “Generating Random Elements of a Finite Group”

[6] http://en.wikipedia.org/wiki/Block_%28permutation_group_theory%29

[7] http://www.algorithmist.com/index.php/Union_Find

[8] http://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_groups

[9] http://en.wikipedia.org/wiki/Center_%28group_theory%29

[10] http://en.wikipedia.org/wiki/Centralizer_and_normalizer

[11] http://groupprops.subwiki.org/wiki/Derived_subgroup

[12] http://en.wikipedia.org/wiki/Nilpotent_group

[13] http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf

property base

Return a base from the Schreier-Sims algorithm.

For a permutation group G, a base is a sequence of points B = (b_1, b_2, …, b_k) such that no element of G apart from the identity fixes all the points in B. The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.

An alternative way to think of B is that it gives the indices of the stabilizer cosets that contain more than the identity permutation.

Examples

>>> from ..combinatorics import Permutation, PermutationGroup
>>> G = PermutationGroup([Permutation(0, 1, 3)(2, 4)])
>>> G.base
[0, 2]

See also

strong_gens, basic_transversals, basic_orbits, basic_stabilizers

baseswap(base, strong_gens, pos, randomized=False, transversals=None, basic_orbits=None, strong_gens_distr=None)

Swap two consecutive base points in base and strong generating set.

If a base for a group G is given by (b_1, b_2, …, b_k), this function returns a base (b_1, b_2, …, b_{i+1}, b_i, …, b_k), where i is given by pos, and a strong generating set relative to that base. The original base and strong generating set are not modified.

The randomized version (default) is of Las Vegas type.

Parameters:

• base – The base and strong generating set.

• strong_gens – The base and strong generating set.

• pos – The position at which swapping is performed.

• randomized – A switch between randomized and deterministic version.

• transversals – The transversals for the basic orbits, if known.

• basic_orbits – The basic orbits, if known.

• strong_gens_distr – The strong generators distributed by basic stabilizers, if known.

Returns:

base is the new base, and strong_gens is a generating set relative to it.

Return type:

(base, strong_gens)

Examples

>>> from .named_groups import SymmetricGroup
>>> from .testutil import _verify_bsgs
>>> from .perm_groups import PermutationGroup
>>> S = SymmetricGroup(4)
>>> S.schreier_sims()
>>> S.base
[0, 1, 2]
>>> base, gens = S.baseswap(S.base, S.strong_gens, 1, randomized=False)
>>> base, gens
([0, 2, 1],
[(0 1 2 3), (3)(0 1), (1 3 2),
 (2 3), (1 3)])

check that base, gens is a BSGS

>>> S1 = PermutationGroup(gens)
>>> _verify_bsgs(S1, base, gens)
True

See also

schreier_sims

Notes

The deterministic version of the algorithm is discussed in [1], pp. 102-103; the randomized version is discussed in [1], p.103, and [2], p.98. It is of Las Vegas type. Notice that [1] contains a mistake in the pseudocode and discussion of BASESWAP: on line 3 of the pseudocode, |beta_{i+1}^{leftlangle Trightrangle}| should be replaced by |beta_{i}^{leftlangle Trightrangle}|, and the same for the discussion of the algorithm.

property basic_orbits

Return the basic orbits relative to a base and strong generating set.

If (b_1, b_2, …, b_k) is a base for a group G, and G^{(i)} = G_{b_1, b_2, …, b_{i-1}} is the i-th basic stabilizer (so that G^{(1)} = G), the i-th basic orbit relative to this base is the orbit of b_i under G^{(i)}. See [1], pp. 87-89 for more information.

Examples

>>> from .named_groups import SymmetricGroup
>>> S = SymmetricGroup(4)
>>> S.basic_orbits
[[0, 1, 2, 3], [1, 2, 3], [2, 3]]

See also

base, strong_gens, basic_transversals, basic_stabilizers

property basic_stabilizers

Return a chain of stabilizers relative to a base and strong generating set.

The i-th basic stabilizer G^{(i)} relative to a base (b_1, b_2, …, b_k) is G_{b_1, b_2, …, b_{i-1}}. For more information, see [1], pp. 87-89.

Examples

>>> from .named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.schreier_sims()
>>> A.base
[0, 1]
>>> for g in A.basic_stabilizers:
...     print(g)
...
PermutationGroup([
    (3)(0 1 2),
    (1 2 3)])
PermutationGroup([
    (1 2 3)])

See also

base, strong_gens, basic_orbits, basic_transversals

property basic_transversals

Return basic transversals relative to a base and strong generating set.

The basic transversals are transversals of the basic orbits. They are provided as a list of dictionaries, each dictionary having keys - the elements of one of the basic orbits, and values - the corresponding transversal elements. See [1], pp. 87-89 for more information.

Examples

>>> from .named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.basic_transversals
[{0: (3), 1: (3)(0 1 2), 2: (3)(0 2 1), 3: (0 3 1)}, {1: (3), 2: (1 2 3), 3: (1 3 2)}]

See also

strong_gens, base, basic_orbits, basic_stabilizers

center()

Return the center of a permutation group.

The center for a group G is defined as Z(G) = {zin G | forall gin G, zg = gz }, the set of elements of G that commute with all elements of G. It is equal to the centralizer of G inside G, and is naturally a subgroup of G ([9]).

Examples

>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> G = D.center()
>>> G.order()
2

See also

centralizer

Notes

This is a naive implementation that is a straightforward application of .centralizer()

centralizer(other)

Return the centralizer of a group/set/element.

The centralizer of a set of permutations S inside a group G is the set of elements of G that commute with all elements of S:

`C_G(S) = \{ g \in G | gs = sg \forall s \in S\}` ([10])

Usually, S is a subset of G, but if G is a proper subgroup of the full symmetric group, we allow for S to have elements outside G.

It is naturally a subgroup of G; the centralizer of a permutation group is equal to the centralizer of any set of generators for that group, since any element commuting with the generators commutes with any product of the generators.

Parameters:

other – a permutation group/list of permutations/single permutation

Examples

>>> from .named_groups import (SymmetricGroup,
... CyclicGroup)
>>> S = SymmetricGroup(6)
>>> C = CyclicGroup(6)
>>> H = S.centralizer(C)
>>> H.is_subgroup(C)
True

See also

subgroup_search

Notes

The implementation is an application of .subgroup_search() with tests using a specific base for the group G.

commutator(G, H)

Return the commutator of two subgroups.

For a permutation group K and subgroups G, H, the commutator of G and H is defined as the group generated by all the commutators [g, h] = hgh^{-1}g^{-1} for g in G and h in H. It is naturally a subgroup of K ([1], p.27).

Examples

>>> from .named_groups import (SymmetricGroup,
... AlternatingGroup)
>>> S = SymmetricGroup(5)
>>> A = AlternatingGroup(5)
>>> G = S.commutator(S, A)
>>> G.is_subgroup(A)
True

See also

derived_subgroup

Notes

The commutator of two subgroups H, G is equal to the normal closure of the commutators of all the generators, i.e. hgh^{-1}g^{-1} for h a generator of H and g a generator of G ([1], p.28)

contains(g, strict=True)

Test if permutation g belong to self, G.

If g is an element of G it can be written as a product of factors drawn from the cosets of G’s stabilizers. To see if g is one of the actual generators defining the group use G.has(g).

If strict is not True, g will be resized, if necessary, to match the size of permutations in self.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup

>>> a = Permutation(1, 2)
>>> b = Permutation(2, 3, 1)
>>> G = PermutationGroup(a, b, degree=5)
>>> G.contains(G[0]) # trivial check
True
>>> elem = Permutation([[2, 3]], size=5)
>>> G.contains(elem)
True
>>> G.contains(Permutation(4)(0, 1, 2, 3))
False

If strict is False, a permutation will be resized, if necessary:

>>> H = PermutationGroup(Permutation(5))
>>> H.contains(Permutation(3))
False
>>> H.contains(Permutation(3), strict=False)
True

To test if a given permutation is present in the group:

>>> elem in G.generators
False
>>> G.has(elem)
False

See also

coset_factor, has, in

coset_factor(g, factor_index=False)

Return G’s (self’s) coset factorization of g

If g is an element of G then it can be written as the product of permutations drawn from the Schreier-Sims coset decomposition,

The permutations returned in f are those for which the product gives g: g = f[n]*...f[1]*f[0] where n = len(B) and B = G.base. f[i] is one of the permutations in self._basic_orbits[i].

If factor_index==True, returns a tuple [b[0],..,b[n]], where b[i] belongs to self._basic_orbits[i]

Examples

>>> from ..combinatorics import Permutation, PermutationGroup
>>> Permutation.print_cyclic = True
>>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5)
>>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6)
>>> G = PermutationGroup([a, b])

Define g:

>>> g = Permutation(7)(1, 2, 4)(3, 6, 5)

Confirm that it is an element of G:

>>> G.contains(g)
True

Thus, it can be written as a product of factors (up to 3) drawn from u. See below that a factor from u1 and u2 and the Identity permutation have been used:

>>> f = G.coset_factor(g)
>>> f[2]*f[1]*f[0] == g
True
>>> f1 = G.coset_factor(g, True); f1
[0, 4, 4]
>>> tr = G.basic_transversals
>>> f[0] == tr[0][f1[0]]
True

If g is not an element of G then [] is returned:

>>> c = Permutation(5, 6, 7)
>>> G.coset_factor(c)
[]

see util._strip

coset_rank(g)

rank using Schreier-Sims representation

The coset rank of g is the ordering number in which it appears in the lexicographic listing according to the coset decomposition

The ordering is the same as in G.generate(method=’coset’). If g does not belong to the group it returns None.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5)
>>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6)
>>> G = PermutationGroup([a, b])
>>> c = Permutation(7)(2, 4)(3, 5)
>>> G.coset_rank(c)
16
>>> G.coset_unrank(16)
(7)(2 4)(3 5)

See also

coset_factor

coset_table(H)

Return the standardised (right) coset table of self in H as a list of lists.

coset_transversal(H)

Return a transversal of the right cosets of self by its subgroup H using the second method described in [1], Subsection 4.6.7

coset_unrank(rank, af=False)

unrank using Schreier-Sims representation

coset_unrank is the inverse operation of coset_rank if 0 <= rank < order; otherwise it returns None.

default_assumptions = {}

property degree

Returns the size of the permutations in the group.

The number of permutations comprising the group is given by len(group); the number of permutations that can be generated by the group is given by group.order().

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([1, 0, 2])
>>> G = PermutationGroup([a])
>>> G.degree
3
>>> len(G)
1
>>> G.order()
2
>>> list(G.generate())
[(2), (2)(0 1)]

See also

order

derived_series()

Return the derived series for the group.

The derived series for a group G is defined as G = G_0 > G_1 > G_2 > ldots where G_i = [G_{i-1}, G_{i-1}], i.e. G_i is the derived subgroup of G_{i-1}, for iinmathbb{N}. When we have G_k = G_{k-1} for some kinmathbb{N}, the series terminates.

Returns:

• A list of permutation groups containing the members of the derived

• series in the order G = G_0, G_1, G_2, ldots.

Examples

>>> from .named_groups import (SymmetricGroup,
... AlternatingGroup, DihedralGroup)
>>> A = AlternatingGroup(5)
>>> len(A.derived_series())
1
>>> S = SymmetricGroup(4)
>>> len(S.derived_series())
4
>>> S.derived_series()[1].is_subgroup(AlternatingGroup(4))
True
>>> S.derived_series()[2].is_subgroup(DihedralGroup(2))
True

See also

derived_subgroup

derived_subgroup()

Compute the derived subgroup.

The derived subgroup, or commutator subgroup is the subgroup generated by all commutators [g, h] = hgh^{-1}g^{-1} for g, hin G ; it is equal to the normal closure of the set of commutators of the generators ([1], p.28, [11]).

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([1, 0, 2, 4, 3])
>>> b = Permutation([0, 1, 3, 2, 4])
>>> G = PermutationGroup([a, b])
>>> C = G.derived_subgroup()
>>> list(C.generate(af=True))
[[0, 1, 2, 3, 4], [0, 1, 3, 4, 2], [0, 1, 4, 2, 3]]

See also

derived_series

property elements

Returns all the elements of the permutation group as a set

Examples

>>> from ..combinatorics import Permutation, PermutationGroup
>>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2))
>>> p.elements
{(3), (2 3), (3)(1 2), (1 2 3), (1 3 2), (1 3)}

generate(method='coset', af=False)

Return iterator to generate the elements of the group

Iteration is done with one of these methods:

method='coset'  using the Schreier-Sims coset representation
method='dimino' using the Dimino method

If af = True it yields the array form of the permutations

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from ..combinatorics import PermutationGroup
>>> from .polyhedron import tetrahedron

The permutation group given in the tetrahedron object is also true groups:

>>> G = tetrahedron.pgroup
>>> G.is_group
True

Also the group generated by the permutations in the tetrahedron pgroup – even the first two – is a proper group:

>>> H = PermutationGroup(G[0], G[1])
>>> J = PermutationGroup(list(H.generate())); J
PermutationGroup([
    (0 1)(2 3),
    (3),
    (1 2 3),
    (1 3 2),
    (0 3 1),
    (0 2 3),
    (0 3)(1 2),
    (0 1 3),
    (3)(0 2 1),
    (0 3 2),
    (3)(0 1 2),
    (0 2)(1 3)])
>>> _.is_group
True

generate_dimino(af=False)

Yield group elements using Dimino’s algorithm

If af == True it yields the array form of the permutations

References

[1] The Implementation of Various Algorithms for Permutation Groups in the Computer Algebra System: AXIOM, N.J. Doye, M.Sc. Thesis

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1, 3])
>>> b = Permutation([0, 2, 3, 1])
>>> g = PermutationGroup([a, b])
>>> list(g.generate_dimino(af=True))
[[0, 1, 2, 3], [0, 2, 1, 3], [0, 2, 3, 1],
 [0, 1, 3, 2], [0, 3, 2, 1], [0, 3, 1, 2]]

generate_schreier_sims(af=False)

Yield group elements using the Schreier-Sims representation in coset_rank order

If af = True it yields the array form of the permutations

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1, 3])
>>> b = Permutation([0, 2, 3, 1])
>>> g = PermutationGroup([a, b])
>>> list(g.generate_schreier_sims(af=True))
[[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 2, 1],
 [0, 1, 3, 2], [0, 2, 3, 1], [0, 3, 1, 2]]

property generators

Returns the generators of the group.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.generators
[(1 2), (2)(0 1)]

property is_abelian

Test if the group is Abelian.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.is_abelian
False
>>> a = Permutation([0, 2, 1])
>>> G = PermutationGroup([a])
>>> G.is_abelian
True

is_alt_sym(eps=0.05, _random_prec=None)

Monte Carlo test for the symmetric/alternating group for degrees >= 8.

More specifically, it is one-sided Monte Carlo with the answer True (i.e., G is symmetric/alternating) guaranteed to be correct, and the answer False being incorrect with probability eps.

Notes

The algorithm itself uses some nontrivial results from group theory and number theory: 1) If a transitive group G of degree n contains an element with a cycle of length n/2 < p < n-2 for p a prime, G is the symmetric or alternating group ([1], pp. 81-82) 2) The proportion of elements in the symmetric/alternating group having the property described in 1) is approximately log(2)/log(n) ([1], p.82; [2], pp. 226-227). The helper function _check_cycles_alt_sym is used to go over the cycles in a permutation and look for ones satisfying 1).

Examples

>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.is_alt_sym()
False

See also

_check_cycles_alt_sym

is_group = True

property is_nilpotent

Test if the group is nilpotent.

A group G is nilpotent if it has a central series of finite length. Alternatively, G is nilpotent if its lower central series terminates with the trivial group. Every nilpotent group is also solvable ([1], p.29, [12]).

Examples

>>> from .named_groups import (SymmetricGroup,
... CyclicGroup)
>>> C = CyclicGroup(6)
>>> C.is_nilpotent
True
>>> S = SymmetricGroup(5)
>>> S.is_nilpotent
False

See also

lower_central_series, is_solvable

is_normal(gr, strict=True)

Test if G=self is a normal subgroup of gr.

G is normal in gr if for each g2 in G, g1 in gr, g = g1*g2*g1**-1 belongs to G It is sufficient to check this for each g1 in gr.generators and g2 in G.generators.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([1, 2, 0])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G1 = PermutationGroup([a, Permutation([2, 0, 1])])
>>> G1.is_normal(G)
True

is_primitive(randomized=True)

Test if a group is primitive.

A permutation group G acting on a set S is called primitive if S contains no nontrivial block under the action of G (a block is nontrivial if its cardinality is more than 1).

Notes

The algorithm is described in [1], p.83, and uses the function minimal_block to search for blocks of the form {0, k} for k ranging over representatives for the orbits of G_0, the stabilizer of 0. This algorithm has complexity O(n^2) where n is the degree of the group, and will perform badly if G_0 is small.

There are two implementations offered: one finds G_0 deterministically using the function stabilizer, and the other (default) produces random elements of G_0 using random_stab, hoping that they generate a subgroup of G_0 with not too many more orbits than G_0 (this is suggested in [1], p.83). Behavior is changed by the randomized flag.

Examples

>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.is_primitive()
False

See also

minimal_block, random_stab

property is_solvable

Test if the group is solvable.

G is solvable if its derived series terminates with the trivial group ([1], p.29).

Examples

>>> from .named_groups import SymmetricGroup
>>> S = SymmetricGroup(3)
>>> S.is_solvable
True

See also

is_nilpotent, derived_series

is_subgroup(G, strict=True)

Return True if all elements of self belong to G.

If strict is False then if self’s degree is smaller than G’s, the elements will be resized to have the same degree.

Examples

>>> from ..combinatorics import Permutation, PermutationGroup
>>> from .named_groups import (SymmetricGroup,
...    CyclicGroup)

Testing is strict by default: the degree of each group must be the same:

>>> p = Permutation(0, 1, 2, 3, 4, 5)
>>> G1 = PermutationGroup([Permutation(0, 1, 2), Permutation(0, 1)])
>>> G2 = PermutationGroup([Permutation(0, 2), Permutation(0, 1, 2)])
>>> G3 = PermutationGroup([p, p**2])
>>> assert G1.order() == G2.order() == G3.order() == 6
>>> G1.is_subgroup(G2)
True
>>> G1.is_subgroup(G3)
False
>>> G3.is_subgroup(PermutationGroup(G3[1]))
False
>>> G3.is_subgroup(PermutationGroup(G3[0]))
True

To ignore the size, set strict to False:

>>> S3 = SymmetricGroup(3)
>>> S5 = SymmetricGroup(5)
>>> S3.is_subgroup(S5, strict=False)
True
>>> C7 = CyclicGroup(7)
>>> G = S5*C7
>>> S5.is_subgroup(G, False)
True
>>> C7.is_subgroup(G, 0)
False

is_transitive(strict=True)

Test if the group is transitive.

A group is transitive if it has a single orbit.

If strict is False the group is transitive if it has a single orbit of length different from 1.

Examples

>>> from .permutations import Permutation
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1, 3])
>>> b = Permutation([2, 0, 1, 3])
>>> G1 = PermutationGroup([a, b])
>>> G1.is_transitive()
False
>>> G1.is_transitive(strict=False)
True
>>> c = Permutation([2, 3, 0, 1])
>>> G2 = PermutationGroup([a, c])
>>> G2.is_transitive()
True
>>> d = Permutation([1, 0, 2, 3])
>>> e = Permutation([0, 1, 3, 2])
>>> G3 = PermutationGroup([d, e])
>>> G3.is_transitive() or G3.is_transitive(strict=False)
False

property is_trivial

Test if the group is the trivial group.

This is true if the group contains only the identity permutation.

Examples

>>> from ..combinatorics import Permutation
>>> from .perm_groups import PermutationGroup
>>> G = PermutationGroup([Permutation([0, 1, 2])])
>>> G.is_trivial
True

lower_central_series()

Return the lower central series for the group.

The lower central series for a group G is the series G = G_0 > G_1 > G_2 > ldots where G_k = [G, G_{k-1}], i.e. every term after the first is equal to the commutator of G and the previous term in G1 ([1], p.29).

Return type:

A list of permutation groups in the order G = G_0, G_1, G_2, ldots

Examples

>>> from .named_groups import (AlternatingGroup,
... DihedralGroup)
>>> A = AlternatingGroup(4)
>>> len(A.lower_central_series())
2
>>> A.lower_central_series()[1].is_subgroup(DihedralGroup(2))
True

See also

commutator, derived_series

make_perm(n, seed=None)

Multiply n randomly selected permutations from pgroup together, starting with the identity permutation. If n is a list of integers, those integers will be used to select the permutations and they will be applied in L to R order: make_perm((A, B, C)) will give CBA(I) where I is the identity permutation.

seed is used to set the seed for the random selection of permutations from pgroup. If this is a list of integers, the corresponding permutations from pgroup will be selected in the order give. This is mainly used for testing purposes.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> a, b = [Permutation([1, 0, 3, 2]), Permutation([1, 3, 0, 2])]
>>> G = PermutationGroup([a, b])
>>> G.make_perm(1, [0])
(0 1)(2 3)
>>> G.make_perm(3, [0, 1, 0])
(0 2 3 1)
>>> G.make_perm([0, 1, 0])
(0 2 3 1)

See also

random

property max_div

Maximum proper divisor of the degree of a permutation group.

Notes

Obviously, this is the degree divided by its minimal proper divisor (larger than 1, if one exists). As it is guaranteed to be prime, the sieve from sympy.ntheory is used. This function is also used as an optimization tool for the functions minimal_block and _union_find_merge.

Examples

>>> from ..combinatorics import Permutation
>>> from .perm_groups import PermutationGroup
>>> G = PermutationGroup([Permutation([0, 2, 1, 3])])
>>> G.max_div
2

See also

minimal_block, _union_find_merge

minimal_block(points)

For a transitive group, finds the block system generated by points.

If a group G acts on a set S, a nonempty subset B of S is called a block under the action of G if for all g in G we have gB = B (g fixes B) or gB and B have no common points (g moves B entirely). ([1], p.23; [6]).

The distinct translates gB of a block B for g in G partition the set S and this set of translates is known as a block system. Moreover, we obviously have that all blocks in the partition have the same size, hence the block size divides |S| ([1], p.23). A G-congruence is an equivalence relation ~ on the set S such that a ~ b implies g(a) ~ g(b) for all g in G. For a transitive group, the equivalence classes of a G-congruence and the blocks of a block system are the same thing ([1], p.23).

The algorithm below checks the group for transitivity, and then finds the G-congruence generated by the pairs (p_0, p_1), (p_0, p_2), ..., (p_0,p_{k-1}) which is the same as finding the maximal block system (i.e., the one with minimum block size) such that p_0, ..., p_{k-1} are in the same block ([1], p.83).

It is an implementation of Atkinson’s algorithm, as suggested in [1], and manipulates an equivalence relation on the set S using a union-find data structure. The running time is just above O(|points||S|). ([1], pp. 83-87; [7]).

Examples

>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.minimal_block([0, 5])
[0, 6, 2, 8, 4, 0, 6, 2, 8, 4]
>>> D.minimal_block([0, 1])
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

See also

_union_find_rep, _union_find_merge, is_transitive, is_primitive

normal_closure(other, k=10)

Return the normal closure of a subgroup/set of permutations.

If S is a subset of a group G, the normal closure of A in G is defined as the intersection of all normal subgroups of G that contain A ([1], p.14). Alternatively, it is the group generated by the conjugates x^{-1}yx for x a generator of G and y a generator of the subgroup \left\langle S\right\rangle generated by S (for some chosen generating set for \left\langle S\right\rangle) ([1], p.73).

Parameters:

• other – a subgroup/list of permutations/single permutation

• k – an implementation-specific parameter that determines the number of conjugates that are adjoined to other at once

Examples

>>> from .named_groups import (SymmetricGroup,
... CyclicGroup, AlternatingGroup)
>>> S = SymmetricGroup(5)
>>> C = CyclicGroup(5)
>>> G = S.normal_closure(C)
>>> G.order()
60
>>> G.is_subgroup(AlternatingGroup(5))
True

See also

commutator, derived_subgroup, random_pr

Notes

The algorithm is described in [1], pp. 73-74; it makes use of the generation of random elements for permutation groups by the product replacement algorithm.

orbit(alpha, action='tuples')

Compute the orbit of alpha {g(alpha) | g in G} as a set.

The time complexity of the algorithm used here is O(|Orb|*r) where |Orb| is the size of the orbit and r is the number of generators of the group. For a more detailed analysis, see [1], p.78, [2], pp. 19-21. Here alpha can be a single point, or a list of points.

If alpha is a single point, the ordinary orbit is computed. if alpha is a list of points, there are three available options:

‘union’ - computes the union of the orbits of the points in the list ‘tuples’ - computes the orbit of the list interpreted as an ordered tuple under the group action ( i.e., g((1,2,3)) = (g(1), g(2), g(3)) ) ‘sets’ - computes the orbit of the list interpreted as a sets

Examples

>>> from ..combinatorics import Permutation
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([1, 2, 0, 4, 5, 6, 3])
>>> G = PermutationGroup([a])
>>> G.orbit(0)
{0, 1, 2}
>>> G.orbit([0, 4], 'union')
{0, 1, 2, 3, 4, 5, 6}

See also

orbit_transversal

orbit_rep(alpha, beta, schreier_vector=None)

Return a group element which sends alpha to beta.

If beta is not in the orbit of alpha, the function returns False. This implementation makes use of the schreier vector. For a proof of correctness, see [1], p.80

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> from .named_groups import AlternatingGroup
>>> G = AlternatingGroup(5)
>>> G.orbit_rep(0, 4)
(0 4 1 2 3)

See also

schreier_vector

orbit_transversal(alpha, pairs=False)

Computes a transversal for the orbit of alpha as a set.

For a permutation group G, a transversal for the orbit Orb = {g(alpha) | g in G} is a set {g_beta | g_beta(alpha) = beta} for beta in Orb. Note that there may be more than one possible transversal. If pairs is set to True, it returns the list of pairs (beta, g_beta). For a proof of correctness, see [1], p.79

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> G = DihedralGroup(6)
>>> G.orbit_transversal(0)
[(5), (0 1 2 3 4 5), (0 5)(1 4)(2 3), (0 2 4)(1 3 5), (5)(0 4)(1 3), (0 3)(1 4)(2 5)]

See also

orbit

orbits(rep=False)

Return the orbits of self, ordered according to lowest element in each orbit.

Examples

>>> from .permutations import Permutation
>>> from .perm_groups import PermutationGroup
>>> a = Permutation(1, 5)(2, 3)(4, 0, 6)
>>> b = Permutation(1, 5)(3, 4)(2, 6, 0)
>>> G = PermutationGroup([a, b])
>>> G.orbits()
[{0, 2, 3, 4, 6}, {1, 5}]

order()

Return the order of the group: the number of permutations that can be generated from elements of the group.

The number of permutations comprising the group is given by len(group); the length of each permutation in the group is given by group.size.

Examples

>>> from .permutations import Permutation
>>> from .perm_groups import PermutationGroup

>>> a = Permutation([1, 0, 2])
>>> G = PermutationGroup([a])
>>> G.degree
3
>>> len(G)
1
>>> G.order()
2
>>> list(G.generate())
[(2), (2)(0 1)]

>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.order()
6

See also

degree

pointwise_stabilizer(points, incremental=True)

Return the pointwise stabilizer for a set of points.

For a permutation group G and a set of points {p_1, p_2,ldots, p_k}, the pointwise stabilizer of p_1, p_2, ldots, p_k is defined as G_{p_1,ldots, p_k} = {gin G | g(p_i) = p_i forall iin{1, 2,ldots,k}} ([1],p20). It is a subgroup of G.

Examples

>>> from .named_groups import SymmetricGroup
>>> S = SymmetricGroup(7)
>>> Stab = S.pointwise_stabilizer([2, 3, 5])
>>> Stab.is_subgroup(S.stabilizer(2).stabilizer(3).stabilizer(5))
True

See also

stabilizer, schreier_sims_incremental

Notes

When incremental == True, rather than the obvious implementation using successive calls to .stabilizer(), this uses the incremental Schreier-Sims algorithm to obtain a base with starting segment - the given points.

random(af=False)

Return a random group element

random_pr(gen_count=11, iterations=50, _random_prec=None)

Return a random group element using product replacement.

For the details of the product replacement algorithm, see _random_pr_init In random_pr the actual ‘product replacement’ is performed. Notice that if the attribute _random_gens is empty, it needs to be initialized by _random_pr_init.

See also

_random_pr_init

random_stab(alpha, schreier_vector=None, _random_prec=None)

Random element from the stabilizer of alpha.

The schreier vector for alpha is an optional argument used for speeding up repeated calls. The algorithm is described in [1], p.81

See also

random_pr, orbit_rep

schreier_sims()

Schreier-Sims algorithm.

It computes the generators of the chain of stabilizers G > G_{b_1} > .. > G_{b1,..,b_r} > 1 in which G_{b_1,..,b_i} stabilizes b_1,..,b_i, and the corresponding s cosets. An element of the group can be written as the product h_1*..*h_s.

We use the incremental Schreier-Sims algorithm.

Examples

>>> from .permutations import Permutation
>>> from .perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.schreier_sims()
>>> G.basic_transversals
[{0: (2)(0 1), 1: (2), 2: (1 2)},
 {0: (2), 2: (0 2)}]

schreier_sims_incremental(base=None, gens=None)

Extend a sequence of points and generating set to a base and strong generating set.

Parameters:

• base – The sequence of points to be extended to a base. Optional parameter with default value [].

• gens – The generating set to be extended to a strong generating set relative to the base obtained. Optional parameter with default value self.generators.

Returns:

base is the base obtained, and strong_gens is the strong generating set relative to it. The original parameters base, gens remain unchanged.

Return type:

(base, strong_gens)

Examples

>>> from .named_groups import AlternatingGroup
>>> from .perm_groups import PermutationGroup
>>> from .testutil import _verify_bsgs
>>> A = AlternatingGroup(7)
>>> base = [2, 3]
>>> seq = [2, 3]
>>> base, strong_gens = A.schreier_sims_incremental(base=seq)
>>> _verify_bsgs(A, base, strong_gens)
True
>>> base[:2]
[2, 3]

Notes

This version of the Schreier-Sims algorithm runs in polynomial time. There are certain assumptions in the implementation - if the trivial group is provided, base and gens are returned immediately, as any sequence of points is a base for the trivial group. If the identity is present in the generators gens, it is removed as it is a redundant generator. The implementation is described in [1], pp. 90-93.

See also

schreier_sims, schreier_sims_random

schreier_sims_random(base=None, gens=None, consec_succ=10, _random_prec=None)

Randomized Schreier-Sims algorithm.

The randomized Schreier-Sims algorithm takes the sequence base and the generating set gens, and extends base to a base, and gens to a strong generating set relative to that base with probability of a wrong answer at most 2^{-consec_succ}, provided the random generators are sufficiently random.

Parameters:

• base – The sequence to be extended to a base.

• gens – The generating set to be extended to a strong generating set.

• consec_succ – The parameter defining the probability of a wrong answer.

• _random_prec – An internal parameter used for testing purposes.

Returns:

base is the base and strong_gens is the strong generating set relative to it.

Return type:

(base, strong_gens)

Examples

>>> from .perm_groups import PermutationGroup
>>> from .testutil import _verify_bsgs
>>> from .named_groups import SymmetricGroup
>>> S = SymmetricGroup(5)
>>> base, strong_gens = S.schreier_sims_random(consec_succ=5)
>>> _verify_bsgs(S, base, strong_gens) 
True

Notes

The algorithm is described in detail in [1], pp. 97-98. It extends the orbits orbs and the permutation groups stabs to basic orbits and basic stabilizers for the base and strong generating set produced in the end. The idea of the extension process is to “sift” random group elements through the stabilizer chain and amend the stabilizers/orbits along the way when a sift is not successful. The helper function _strip is used to attempt to decompose a random group element according to the current state of the stabilizer chain and report whether the element was fully decomposed (successful sift) or not (unsuccessful sift). In the latter case, the level at which the sift failed is reported and used to amend stabs, base, gens and orbs accordingly. The halting condition is for consec_succ consecutive successful sifts to pass. This makes sure that the current base and gens form a BSGS with probability at least 1 - 1/text{consec_succ}.

See also

schreier_sims

schreier_vector(alpha)

Computes the schreier vector for alpha.

The Schreier vector efficiently stores information about the orbit of alpha. It can later be used to quickly obtain elements of the group that send alpha to a particular element in the orbit. Notice that the Schreier vector depends on the order in which the group generators are listed. For a definition, see [3]. Since list indices start from zero, we adopt the convention to use “None” instead of 0 to signify that an element doesn’t belong to the orbit. For the algorithm and its correctness, see [2], pp.78-80.

Examples

>>> from .perm_groups import PermutationGroup
>>> from .permutations import Permutation
>>> a = Permutation([2, 4, 6, 3, 1, 5, 0])
>>> b = Permutation([0, 1, 3, 5, 4, 6, 2])
>>> G = PermutationGroup([a, b])
>>> G.schreier_vector(0)
[-1, None, 0, 1, None, 1, 0]

See also

orbit

stabilizer(alpha)

Return the stabilizer subgroup of alpha.

The stabilizer of alpha is the group G_alpha = {g in G | g(alpha) = alpha}. For a proof of correctness, see [1], p.79.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from .perm_groups import PermutationGroup
>>> from .named_groups import DihedralGroup
>>> G = DihedralGroup(6)
>>> G.stabilizer(5)
PermutationGroup([
    (5)(0 4)(1 3),
    (5)])

See also

orbit

property strong_gens

Return a strong generating set from the Schreier-Sims algorithm.

A generating set S = {g_1, g_2, …, g_t} for a permutation group G is a strong generating set relative to the sequence of points (referred to as a “base”) (b_1, b_2, …, b_k) if, for 1 leq i leq k we have that the intersection of the pointwise stabilizer G^{(i+1)} := G_{b_1, b_2, …, b_i} with S generates the pointwise stabilizer G^{(i+1)}. The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.

Examples

>>> from .named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> D.strong_gens
[(0 1 2 3), (0 3)(1 2), (1 3)]
>>> D.base
[0, 1]

See also

base, basic_transversals, basic_orbits, basic_stabilizers

subgroup(gens)

Return the subgroup generated by gens which is a list of elements of the group

subgroup_search(prop, base=None, strong_gens=None, tests=None, init_subgroup=None)

Find the subgroup of all elements satisfying the property prop.

This is done by a depth-first search with respect to base images that uses several tests to prune the search tree.

Parameters:

• prop – The property to be used. Has to be callable on group elements and always return True or False. It is assumed that all group elements satisfying prop indeed form a subgroup.

• base – A base for the supergroup.

• strong_gens – A strong generating set for the supergroup.

• tests – A list of callables of length equal to the length of base. These are used to rule out group elements by partial base images, so that tests[l](g) returns False if the element g is known not to satisfy prop base on where g sends the first l + 1 base points.

• init_subgroup – if a subgroup of the sought group is known in advance, it can be passed to the function as this parameter.

Returns:

The subgroup of all elements satisfying prop. The generating set for this group is guaranteed to be a strong generating set relative to the base base.

Return type:

res

Examples

>>> from .named_groups import (SymmetricGroup,
... AlternatingGroup)
>>> from .perm_groups import PermutationGroup
>>> from .testutil import _verify_bsgs
>>> S = SymmetricGroup(7)
>>> prop_even = lambda x: x.is_even
>>> base, strong_gens = S.schreier_sims_incremental()
>>> G = S.subgroup_search(prop_even, base=base, strong_gens=strong_gens)
>>> G.is_subgroup(AlternatingGroup(7))
True
>>> _verify_bsgs(G, base, G.generators)
True

Notes

This function is extremely lenghty and complicated and will require some careful attention. The implementation is described in [1], pp. 114-117, and the comments for the code here follow the lines of the pseudocode in the book for clarity.

The complexity is exponential in general, since the search process by itself visits all members of the supergroup. However, there are a lot of tests which are used to prune the search tree, and users can define their own tests via the tests parameter, so in practice, and for some computations, it’s not terrible.

A crucial part in the procedure is the frequent base change performed (this is line 11 in the pseudocode) in order to obtain a new basic stabilizer. The book mentiones that this can be done by using .baseswap(...), however the current imlementation uses a more straightforward way to find the next basic stabilizer - calling the function .stabilizer(...) on the previous basic stabilizer.

property transitivity_degree

Compute the degree of transitivity of the group.

A permutation group G acting on Omega = {0, 1, …, n-1} is k-fold transitive, if, for any k points (a_1, a_2, …, a_k)inOmega and any k points (b_1, b_2, …, b_k)inOmega there exists gin G such that g(a_1)=b_1, g(a_2)=b_2, …, g(a_k)=b_k The degree of transitivity of G is the maximum k such that G is k-fold transitive. ([8])

Examples

>>> from .perm_groups import PermutationGroup
>>> from .permutations import Permutation
>>> a = Permutation([1, 2, 0])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.transitivity_degree
3

See also

is_transitive, orbit

modelparameters.sympy.combinatorics.permutations module

class modelparameters.sympy.combinatorics.permutations.Cycle(*args)

Bases: dict

Wrapper around dict which provides the functionality of a disjoint cycle.

A cycle shows the rule to use to move subsets of elements to obtain a permutation. The Cycle class is more flexible than Permutation in that 1) all elements need not be present in order to investigate how multiple cycles act in sequence and 2) it can contain singletons:

>>> from .permutations import Perm, Cycle

A Cycle will automatically parse a cycle given as a tuple on the rhs:

>>> Cycle(1, 2)(2, 3)
(1 3 2)

The identity cycle, Cycle(), can be used to start a product:

>>> Cycle()(1, 2)(2, 3)
(1 3 2)

The array form of a Cycle can be obtained by calling the list method (or passing it to the list function) and all elements from 0 will be shown:

>>> a = Cycle(1, 2)
>>> a.list()
[0, 2, 1]
>>> list(a)
[0, 2, 1]

If a larger (or smaller) range is desired use the list method and provide the desired size – but the Cycle cannot be truncated to a size smaller than the largest element that is out of place:

>>> b = Cycle(2, 4)(1, 2)(3, 1, 4)(1, 3)
>>> b.list()
[0, 2, 1, 3, 4]
>>> b.list(b.size + 1)
[0, 2, 1, 3, 4, 5]
>>> b.list(-1)
[0, 2, 1]

Singletons are not shown when printing with one exception: the largest element is always shown – as a singleton if necessary:

>>> Cycle(1, 4, 10)(4, 5)
(1 5 4 10)
>>> Cycle(1, 2)(4)(5)(10)
(1 2)(10)

The array form can be used to instantiate a Permutation so other properties of the permutation can be investigated:

>>> Perm(Cycle(1, 2)(3, 4).list()).transpositions()
[(1, 2), (3, 4)]

Notes

The underlying structure of the Cycle is a dictionary and although the __iter__ method has been redefined to give the array form of the cycle, the underlying dictionary items are still available with the such methods as items():

>>> list(Cycle(1, 2).items())
[(1, 2), (2, 1)]

See also

Permutation

copy() → a shallow copy of D

list(size=None)

Return the cycles as an explicit list starting from 0 up to the greater of the largest value in the cycles and size.

Truncation of trailing unmoved items will occur when size is less than the maximum element in the cycle; if this is desired, setting size=-1 will guarantee such trimming.

Examples

>>> from .permutations import Cycle
>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Cycle(2, 3)(4, 5)
>>> p.list()
[0, 1, 3, 2, 5, 4]
>>> p.list(10)
[0, 1, 3, 2, 5, 4, 6, 7, 8, 9]

Passing a length too small will trim trailing, unchanged elements in the permutation:

>>> Cycle(2, 4)(1, 2, 4).list(-1)
[0, 2, 1]

property size

modelparameters.sympy.combinatorics.permutations.Perm

alias of Permutation

class modelparameters.sympy.combinatorics.permutations.Permutation(*args, **kwargs)

Bases: Basic

A permutation, alternatively known as an ‘arrangement number’ or ‘ordering’ is an arrangement of the elements of an ordered list into a one-to-one mapping with itself. The permutation of a given arrangement is given by indicating the positions of the elements after re-arrangement [2]. For example, if one started with elements [x, y, a, b] (in that order) and they were reordered as [x, y, b, a] then the permutation would be [0, 1, 3, 2]. Notice that (in SymPy) the first element is always referred to as 0 and the permutation uses the indices of the elements in the original ordering, not the elements (a, b, etc…) themselves.

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = False

Permutations Notation

Permutations are commonly represented in disjoint cycle or array forms.

Array Notation and 2-line Form

In the 2-line form, the elements and their final positions are shown as a matrix with 2 rows:

[0 1 2 … n-1] [p(0) p(1) p(2) … p(n-1)]

Since the first line is always range(n), where n is the size of p, it is sufficient to represent the permutation by the second line, referred to as the “array form” of the permutation. This is entered in brackets as the argument to the Permutation class:

>>> p = Permutation([0, 2, 1]); p
Permutation([0, 2, 1])

Given i in range(p.size), the permutation maps i to i^p

>>> [i^p for i in range(p.size)]
[0, 2, 1]

The composite of two permutations p*q means first apply p, then q, so i^(p*q) = (i^p)^q which is i^p^q according to Python precedence rules:

>>> q = Permutation([2, 1, 0])
>>> [i^p^q for i in range(3)]
[2, 0, 1]
>>> [i^(p*q) for i in range(3)]
[2, 0, 1]

One can use also the notation p(i) = i^p, but then the composition rule is (p*q)(i) = q(p(i)), not p(q(i)):

>>> [(p*q)(i) for i in range(p.size)]
[2, 0, 1]
>>> [q(p(i)) for i in range(p.size)]
[2, 0, 1]
>>> [p(q(i)) for i in range(p.size)]
[1, 2, 0]

Disjoint Cycle Notation

In disjoint cycle notation, only the elements that have shifted are indicated. In the above case, the 2 and 1 switched places. This can be entered in two ways:

>>> Permutation(1, 2) == Permutation([[1, 2]]) == p
True

Only the relative ordering of elements in a cycle matter:

>>> Permutation(1,2,3) == Permutation(2,3,1) == Permutation(3,1,2)
True

The disjoint cycle notation is convenient when representing permutations that have several cycles in them:

>>> Permutation(1, 2)(3, 5) == Permutation([[1, 2], [3, 5]])
True

It also provides some economy in entry when computing products of permutations that are written in disjoint cycle notation:

>>> Permutation(1, 2)(1, 3)(2, 3)
Permutation([0, 3, 2, 1])
>>> _ == Permutation([[1, 2]])*Permutation([[1, 3]])*Permutation([[2, 3]])
True

Caution: when the cycles have common elements between them then the order in which the permutations are applied matters. The convention is that the permutations are applied from right to left. In the following, the transposition of elements 2 and 3 is followed by the transposition of elements 1 and 2:

>>> Permutation(1, 2)(2, 3) == Permutation([(1, 2), (2, 3)])
True
>>> Permutation(1, 2)(2, 3).list()
[0, 3, 1, 2]

If the first and second elements had been swapped first, followed by the swapping of the second and third, the result would have been [0, 2, 3, 1]. If, for some reason, you want to apply the cycles in the order they are entered, you can simply reverse the order of cycles:

>>> Permutation([(1, 2), (2, 3)][::-1]).list()
[0, 2, 3, 1]

Entering a singleton in a permutation is a way to indicate the size of the permutation. The size keyword can also be used.

Array-form entry:

>>> Permutation([[1, 2], [9]])
Permutation([0, 2, 1], size=10)
>>> Permutation([[1, 2]], size=10)
Permutation([0, 2, 1], size=10)

Cyclic-form entry:

>>> Permutation(1, 2, size=10)
Permutation([0, 2, 1], size=10)
>>> Permutation(9)(1, 2)
Permutation([0, 2, 1], size=10)

Caution: no singleton containing an element larger than the largest in any previous cycle can be entered. This is an important difference in how Permutation and Cycle handle the __call__ syntax. A singleton argument at the start of a Permutation performs instantiation of the Permutation and is permitted:

>>> Permutation(5)
Permutation([], size=6)

A singleton entered after instantiation is a call to the permutation – a function call – and if the argument is out of range it will trigger an error. For this reason, it is better to start the cycle with the singleton:

The following fails because there is is no element 3:

>>> Permutation(1, 2)(3)
Traceback (most recent call last):
...
IndexError: list index out of range

This is ok: only the call to an out of range singleton is prohibited; otherwise the permutation autosizes:

>>> Permutation(3)(1, 2)
Permutation([0, 2, 1, 3])
>>> Permutation(1, 2)(3, 4) == Permutation(3, 4)(1, 2)
True

Equality testing

The array forms must be the same in order for permutations to be equal:

>>> Permutation([1, 0, 2, 3]) == Permutation([1, 0])
False

Identity Permutation

The identity permutation is a permutation in which no element is out of place. It can be entered in a variety of ways. All the following create an identity permutation of size 4:

>>> I = Permutation([0, 1, 2, 3])
>>> all(p == I for p in [
... Permutation(3),
... Permutation(range(4)),
... Permutation([], size=4),
... Permutation(size=4)])
True

Watch out for entering the range inside a set of brackets (which is cycle notation):

>>> I == Permutation([range(4)])
False

Permutation Printing

There are a few things to note about how Permutations are printed.

1) If you prefer one form (array or cycle) over another, you can set that with the print_cyclic flag.

>>> Permutation(1, 2)(4, 5)(3, 4)
Permutation([0, 2, 1, 4, 5, 3])
>>> p = _

>>> Permutation.print_cyclic = True
>>> p
(1 2)(3 4 5)
>>> Permutation.print_cyclic = False

2) Regardless of the setting, a list of elements in the array for cyclic form can be obtained and either of those can be copied and supplied as the argument to Permutation:

>>> p.array_form
[0, 2, 1, 4, 5, 3]
>>> p.cyclic_form
[[1, 2], [3, 4, 5]]
>>> Permutation(_) == p
True

3) Printing is economical in that as little as possible is printed while retaining all information about the size of the permutation:

>>> Permutation([1, 0, 2, 3])
Permutation([1, 0, 2, 3])
>>> Permutation([1, 0, 2, 3], size=20)
Permutation([1, 0], size=20)
>>> Permutation([1, 0, 2, 4, 3, 5, 6], size=20)
Permutation([1, 0, 2, 4, 3], size=20)

>>> p = Permutation([1, 0, 2, 3])
>>> Permutation.print_cyclic = True
>>> p
(3)(0 1)
>>> Permutation.print_cyclic = False

The 2 was not printed but it is still there as can be seen with the array_form and size methods:

>>> p.array_form
[1, 0, 2, 3]
>>> p.size
4

Short introduction to other methods

The permutation can act as a bijective function, telling what element is located at a given position

>>> q = Permutation([5, 2, 3, 4, 1, 0])
>>> q.array_form[1] # the hard way
2
>>> q(1) # the easy way
2
>>> {i: q(i) for i in range(q.size)} # showing the bijection
{0: 5, 1: 2, 2: 3, 3: 4, 4: 1, 5: 0}

The full cyclic form (including singletons) can be obtained:

>>> p.full_cyclic_form
[[0, 1], [2], [3]]

Any permutation can be factored into transpositions of pairs of elements:

>>> Permutation([[1, 2], [3, 4, 5]]).transpositions()
[(1, 2), (3, 5), (3, 4)]
>>> Permutation.rmul(*[Permutation([ti], size=6) for ti in _]).cyclic_form
[[1, 2], [3, 4, 5]]

The number of permutations on a set of n elements is given by n! and is called the cardinality.

>>> p.size
4
>>> p.cardinality
24

A given permutation has a rank among all the possible permutations of the same elements, but what that rank is depends on how the permutations are enumerated. (There are a number of different methods of doing so.) The lexicographic rank is given by the rank method and this rank is used to increment a permutation with addition/subtraction:

>>> p.rank()
6
>>> p + 1
Permutation([1, 0, 3, 2])
>>> p.next_lex()
Permutation([1, 0, 3, 2])
>>> _.rank()
7
>>> p.unrank_lex(p.size, rank=7)
Permutation([1, 0, 3, 2])

The product of two permutations p and q is defined as their composition as functions, (p*q)(i) = q(p(i)) [6].

>>> p = Permutation([1, 0, 2, 3])
>>> q = Permutation([2, 3, 1, 0])
>>> list(q*p)
[2, 3, 0, 1]
>>> list(p*q)
[3, 2, 1, 0]
>>> [q(p(i)) for i in range(p.size)]
[3, 2, 1, 0]

The permutation can be ‘applied’ to any list-like object, not only Permutations:

>>> p(['zero', 'one', 'four', 'two'])
 ['one', 'zero', 'four', 'two']
>>> p('zo42')
['o', 'z', '4', '2']

If you have a list of arbitrary elements, the corresponding permutation can be found with the from_sequence method:

>>> Permutation.from_sequence('SymPy')
Permutation([1, 3, 2, 0, 4])

See also

Cycle

References

[1]

Skiena, S. ‘Permutations.’ 1.1 in Implementing Discrete Mathematics Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 3-16, 1990.

[2]

Knuth, D. E. The Art of Computer Programming, Vol. 4: Combinatorial Algorithms, 1st ed. Reading, MA: Addison-Wesley, 2011.

[3]

Wendy Myrvold and Frank Ruskey. 2001. Ranking and unranking permutations in linear time. Inf. Process. Lett. 79, 6 (September 2001), 281-284. DOI=10.1016/S0020-0190(01)00141-7

[4]

D. L. Kreher, D. R. Stinson ‘Combinatorial Algorithms’ CRC Press, 1999

[5]

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

[6]

http://en.wikipedia.org/wiki/Permutation#Product_and_inverse

[7]

http://en.wikipedia.org/wiki/Lehmer_code

property array_form

Return a copy of the attribute _array_form .. rubric:: Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([[2, 0], [3, 1]])
>>> p.array_form
[2, 3, 0, 1]
>>> Permutation([[2, 0, 3, 1]]).array_form
[3, 2, 0, 1]
>>> Permutation([2, 0, 3, 1]).array_form
[2, 0, 3, 1]
>>> Permutation([[1, 2], [4, 5]]).array_form
[0, 2, 1, 3, 5, 4]

ascents()

Returns the positions of ascents in a permutation, ie, the location where p[i] < p[i+1]

Examples

>>> from .permutations import Permutation
>>> p = Permutation([4, 0, 1, 3, 2])
>>> p.ascents()
[1, 2]

See also

descents, inversions, min, max

atoms()

Returns all the elements of a permutation

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([0, 1, 2, 3, 4, 5]).atoms()
{0, 1, 2, 3, 4, 5}
>>> Permutation([[0, 1], [2, 3], [4, 5]]).atoms()
{0, 1, 2, 3, 4, 5}

property cardinality

Returns the number of all possible permutations.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.cardinality
24

See also

length, order, rank, size

commutator(x)

Return the commutator of self and x: ~x*~self*x*self

If f and g are part of a group, G, then the commutator of f and g is the group identity iff f and g commute, i.e. fg == gf.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([0, 2, 3, 1])
>>> x = Permutation([2, 0, 3, 1])
>>> c = p.commutator(x); c
Permutation([2, 1, 3, 0])
>>> c == ~x*~p*x*p
True

>>> I = Permutation(3)
>>> p = [I + i for i in range(6)]
>>> for i in range(len(p)):
...     for j in range(len(p)):
...         c = p[i].commutator(p[j])
...         if p[i]*p[j] == p[j]*p[i]:
...             assert c == I
...         else:
...             assert c != I
...

References

http://en.wikipedia.org/wiki/Commutator

commutes_with(other)

Checks if the elements are commuting.

Examples

>>> from .permutations import Permutation
>>> a = Permutation([1, 4, 3, 0, 2, 5])
>>> b = Permutation([0, 1, 2, 3, 4, 5])
>>> a.commutes_with(b)
True
>>> b = Permutation([2, 3, 5, 4, 1, 0])
>>> a.commutes_with(b)
False

property cycle_structure

Return the cycle structure of the permutation as a dictionary indicating the multiplicity of each cycle length.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> Permutation(3).cycle_structure
{1: 4}
>>> Permutation(0, 4, 3)(1, 2)(5, 6).cycle_structure
{2: 2, 3: 1}

property cycles

Returns the number of cycles contained in the permutation (including singletons).

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([0, 1, 2]).cycles
3
>>> Permutation([0, 1, 2]).full_cyclic_form
[[0], [1], [2]]
>>> Permutation(0, 1)(2, 3).cycles
2

See also

sympy.functions.combinatorial.numbers.stirling

property cyclic_form

This is used to convert to the cyclic notation from the canonical notation. Singletons are omitted.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([0, 3, 1, 2])
>>> p.cyclic_form
[[1, 3, 2]]
>>> Permutation([1, 0, 2, 4, 3, 5]).cyclic_form
[[0, 1], [3, 4]]

See also

array_form, full_cyclic_form

default_assumptions = {}

descents()

Returns the positions of descents in a permutation, ie, the location where p[i] > p[i+1]

Examples

>>> from .permutations import Permutation
>>> p = Permutation([4, 0, 1, 3, 2])
>>> p.descents()
[0, 3]

See also

ascents, inversions, min, max

classmethod from_inversion_vector(inversion)

Calculates the permutation from the inversion vector.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> Permutation.from_inversion_vector([3, 2, 1, 0, 0])
Permutation([3, 2, 1, 0, 4, 5])

classmethod from_sequence(i, key=None)

Return the permutation needed to obtain i from the sorted elements of i. If custom sorting is desired, a key can be given.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.print_cyclic = True

>>> Permutation.from_sequence('SymPy')
(4)(0 1 3)
>>> _(sorted("SymPy"))
['S', 'y', 'm', 'P', 'y']
>>> Permutation.from_sequence('SymPy', key=lambda x: x.lower())
(4)(0 2)(1 3)

property full_cyclic_form

Return permutation in cyclic form including singletons.

Examples

>>> from .permutations import Permutation
>>> Permutation([0, 2, 1]).full_cyclic_form
[[0], [1, 2]]

get_adjacency_distance(other)

Computes the adjacency distance between two permutations.

This metric counts the number of times a pair i,j of jobs is adjacent in both p and p’. If n_adj is this quantity then the adjacency distance is n - n_adj - 1 [1]

[1] Reeves, Colin R. Landscapes, Operators and Heuristic search, Annals of Operational Research, 86, pp 473-490. (1999)

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 3, 1, 2, 4])
>>> q = Permutation.josephus(4, 5, 2)
>>> p.get_adjacency_distance(q)
3
>>> r = Permutation([0, 2, 1, 4, 3])
>>> p.get_adjacency_distance(r)
4

See also

get_precedence_matrix, get_precedence_distance, get_adjacency_matrix

get_adjacency_matrix()

Computes the adjacency matrix of a permutation.

If job i is adjacent to job j in a permutation p then we set m[i, j] = 1 where m is the adjacency matrix of p.

Examples

>>> from .permutations import Permutation
>>> p = Permutation.josephus(3, 6, 1)
>>> p.get_adjacency_matrix()
Matrix([
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0]])
>>> q = Permutation([0, 1, 2, 3])
>>> q.get_adjacency_matrix()
Matrix([
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]])

See also

get_precedence_matrix, get_precedence_distance, get_adjacency_distance

get_positional_distance(other)

Computes the positional distance between two permutations.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 3, 1, 2, 4])
>>> q = Permutation.josephus(4, 5, 2)
>>> r = Permutation([3, 1, 4, 0, 2])
>>> p.get_positional_distance(q)
12
>>> p.get_positional_distance(r)
12

See also

get_precedence_distance, get_adjacency_distance

get_precedence_distance(other)

Computes the precedence distance between two permutations.

Suppose p and p’ represent n jobs. The precedence metric counts the number of times a job j is preceded by job i in both p and p’. This metric is commutative.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([2, 0, 4, 3, 1])
>>> q = Permutation([3, 1, 2, 4, 0])
>>> p.get_precedence_distance(q)
7
>>> q.get_precedence_distance(p)
7

See also

get_precedence_matrix, get_adjacency_matrix, get_adjacency_distance

get_precedence_matrix()

Gets the precedence matrix. This is used for computing the distance between two permutations.

Examples

>>> from .permutations import Permutation
>>> p = Permutation.josephus(3, 6, 1)
>>> p
Permutation([2, 5, 3, 1, 4, 0])
>>> p.get_precedence_matrix()
Matrix([
[0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0],
[1, 1, 0, 1, 1, 1],
[1, 1, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 0]])

See also

get_precedence_distance, get_adjacency_matrix, get_adjacency_distance

index()

Returns the index of a permutation.

The index of a permutation is the sum of all subscripts j such that p[j] is greater than p[j+1].

Examples

>>> from .permutations import Permutation
>>> p = Permutation([3, 0, 2, 1, 4])
>>> p.index()
2

inversion_vector()

Return the inversion vector of the permutation.

The inversion vector consists of elements whose value indicates the number of elements in the permutation that are lesser than it and lie on its right hand side.

The inversion vector is the same as the Lehmer encoding of a permutation.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([4, 8, 0, 7, 1, 5, 3, 6, 2])
>>> p.inversion_vector()
[4, 7, 0, 5, 0, 2, 1, 1]
>>> p = Permutation([3, 2, 1, 0])
>>> p.inversion_vector()
[3, 2, 1]

The inversion vector increases lexicographically with the rank of the permutation, the -ith element cycling through 0..i.

>>> p = Permutation(2)
>>> while p:
...     print('%s %s %s' % (p, p.inversion_vector(), p.rank()))
...     p = p.next_lex()
...
Permutation([0, 1, 2]) [0, 0] 0
Permutation([0, 2, 1]) [0, 1] 1
Permutation([1, 0, 2]) [1, 0] 2
Permutation([1, 2, 0]) [1, 1] 3
Permutation([2, 0, 1]) [2, 0] 4
Permutation([2, 1, 0]) [2, 1] 5

See also

from_inversion_vector

inversions()

Computes the number of inversions of a permutation.

An inversion is where i > j but p[i] < p[j].

For small length of p, it iterates over all i and j values and calculates the number of inversions. For large length of p, it uses a variation of merge sort to calculate the number of inversions.

References

[1] http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3, 4, 5])
>>> p.inversions()
0
>>> Permutation([3, 2, 1, 0]).inversions()
6

See also

descents, ascents, min, max

property is_Empty

Checks to see if the permutation is a set with zero elements

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([]).is_Empty
True
>>> Permutation([0]).is_Empty
False

See also

is_Singleton

property is_Identity

Returns True if the Permutation is an identity permutation.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([])
>>> p.is_Identity
True
>>> p = Permutation([[0], [1], [2]])
>>> p.is_Identity
True
>>> p = Permutation([0, 1, 2])
>>> p.is_Identity
True
>>> p = Permutation([0, 2, 1])
>>> p.is_Identity
False

See also

order

is_Permutation = True

property is_Singleton

Checks to see if the permutation contains only one number and is thus the only possible permutation of this set of numbers

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([0]).is_Singleton
True
>>> Permutation([0, 1]).is_Singleton
False

See also

is_Empty

property is_even

Checks if a permutation is even.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.is_even
True
>>> p = Permutation([3, 2, 1, 0])
>>> p.is_even
True

See also

is_odd

property is_odd

Checks if a permutation is odd.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.is_odd
False
>>> p = Permutation([3, 2, 0, 1])
>>> p.is_odd
True

See also

is_even

classmethod josephus(m, n, s=1)

Return as a permutation the shuffling of range(n) using the Josephus scheme in which every m-th item is selected until all have been chosen. The returned permutation has elements listed by the order in which they were selected.

The parameter s stops the selection process when there are s items remaining and these are selected by continuing the selection, counting by 1 rather than by m.

Consider selecting every 3rd item from 6 until only 2 remain:

choices    chosen
========   ======
  012345
  01 345   2
  01 34    25
  01  4    253
  0   4    2531
  0        25314
           253140

Examples

>>> from ..combinatorics import Permutation
>>> Permutation.josephus(3, 6, 2).array_form
[2, 5, 3, 1, 4, 0]

References

1. http://en.wikipedia.org/wiki/Flavius_Josephus

2. http://en.wikipedia.org/wiki/Josephus_problem

3. http://www.wou.edu/~burtonl/josephus.html

length()

Returns the number of integers moved by a permutation.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([0, 3, 2, 1]).length()
2
>>> Permutation([[0, 1], [2, 3]]).length()
4

See also

min, max, support, cardinality, order, rank, size

list(size=None)

Return the permutation as an explicit list, possibly trimming unmoved elements if size is less than the maximum element in the permutation; if this is desired, setting size=-1 will guarantee such trimming.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation(2, 3)(4, 5)
>>> p.list()
[0, 1, 3, 2, 5, 4]
>>> p.list(10)
[0, 1, 3, 2, 5, 4, 6, 7, 8, 9]

Passing a length too small will trim trailing, unchanged elements in the permutation:

>>> Permutation(2, 4)(1, 2, 4).list(-1)
[0, 2, 1]
>>> Permutation(3).list(-1)
[]

max()

The maximum element moved by the permutation.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([1, 0, 2, 3, 4])
>>> p.max()
1

See also

min, descents, ascents, inversions

min()

The minimum element moved by the permutation.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 4, 3, 2])
>>> p.min()
2

See also

max, descents, ascents, inversions

mul_inv(other)

other*~self, self and other have _array_form

next_lex()

Returns the next permutation in lexicographical order. If self is the last permutation in lexicographical order it returns None. See [4] section 2.4.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([2, 3, 1, 0])
>>> p = Permutation([2, 3, 1, 0]); p.rank()
17
>>> p = p.next_lex(); p.rank()
18

See also

rank, unrank_lex

next_nonlex()

Returns the next permutation in nonlex order [3]. If self is the last permutation in this order it returns None.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([2, 0, 3, 1]); p.rank_nonlex()
5
>>> p = p.next_nonlex(); p
Permutation([3, 0, 1, 2])
>>> p.rank_nonlex()
6

See also

rank_nonlex, unrank_nonlex

next_trotterjohnson()

Returns the next permutation in Trotter-Johnson order. If self is the last permutation it returns None. See [4] section 2.4. If it is desired to generate all such permutations, they can be generated in order more quickly with the generate_bell function.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([3, 0, 2, 1])
>>> p.rank_trotterjohnson()
4
>>> p = p.next_trotterjohnson(); p
Permutation([0, 3, 2, 1])
>>> p.rank_trotterjohnson()
5

See also

rank_trotterjohnson, unrank_trotterjohnson, sympy.utilities.iterables.generate_bell

order()

Computes the order of a permutation.

When the permutation is raised to the power of its order it equals the identity permutation.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> p = Permutation([3, 1, 5, 2, 4, 0])
>>> p.order()
4
>>> (p**(p.order()))
Permutation([], size=6)

See also

identity, cardinality, length, rank, size

parity()

Computes the parity of a permutation.

The parity of a permutation reflects the parity of the number of inversions in the permutation, i.e., the number of pairs of x and y such that x > y but p[x] < p[y].

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.parity()
0
>>> p = Permutation([3, 2, 0, 1])
>>> p.parity()
1

See also

_af_parity

print_cyclic = True

classmethod random(n)

Generates a random permutation of length n.

Uses the underlying Python pseudo-random number generator.

Examples

>>> from .permutations import Permutation
>>> Permutation.random(2) in (Permutation([1, 0]), Permutation([0, 1]))
True

rank()

Returns the lexicographic rank of the permutation.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.rank()
0
>>> p = Permutation([3, 2, 1, 0])
>>> p.rank()
23

See also

next_lex, unrank_lex, cardinality, length, order, size

rank_nonlex(inv_perm=None)

This is a linear time ranking algorithm that does not enforce lexicographic order [3].

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.rank_nonlex()
23

See also

next_nonlex, unrank_nonlex

rank_trotterjohnson()

Returns the Trotter Johnson rank, which we get from the minimal change algorithm. See [4] section 2.4.

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2, 3])
>>> p.rank_trotterjohnson()
0
>>> p = Permutation([0, 2, 1, 3])
>>> p.rank_trotterjohnson()
7

See also

unrank_trotterjohnson, next_trotterjohnson

static rmul(*args)

Return product of Permutations [a, b, c, …] as the Permutation whose ith value is a(b(c(i))).

a, b, c, … can be Permutation objects or tuples.

Examples

>>> from .permutations import _af_rmul, Permutation
>>> Permutation.print_cyclic = False

>>> a, b = [1, 0, 2], [0, 2, 1]
>>> a = Permutation(a); b = Permutation(b)
>>> list(Permutation.rmul(a, b))
[1, 2, 0]
>>> [a(b(i)) for i in range(3)]
[1, 2, 0]

This handles the operands in reverse order compared to the * operator:

>>> a = Permutation(a); b = Permutation(b)
>>> list(a*b)
[2, 0, 1]
>>> [b(a(i)) for i in range(3)]
[2, 0, 1]

Notes

All items in the sequence will be parsed by Permutation as necessary as long as the first item is a Permutation:

>>> Permutation.rmul(a, [0, 2, 1]) == Permutation.rmul(a, b)
True

The reverse order of arguments will raise a TypeError.

classmethod rmul_with_af(*args)

same as rmul, but the elements of args are Permutation objects which have _array_form

runs()

Returns the runs of a permutation.

An ascending sequence in a permutation is called a run [5].

Examples

>>> from .permutations import Permutation
>>> p = Permutation([2, 5, 7, 3, 6, 0, 1, 4, 8])
>>> p.runs()
[[2, 5, 7], [3, 6], [0, 1, 4, 8]]
>>> q = Permutation([1,3,2,0])
>>> q.runs()
[[1, 3], [2], [0]]

signature()

Gives the signature of the permutation needed to place the elements of the permutation in canonical order.

The signature is calculated as (-1)^<number of inversions>

Examples

>>> from .permutations import Permutation
>>> p = Permutation([0, 1, 2])
>>> p.inversions()
0
>>> p.signature()
1
>>> q = Permutation([0,2,1])
>>> q.inversions()
1
>>> q.signature()
-1

See also

inversions

property size

Returns the number of elements in the permutation.

Examples

>>> from ..combinatorics import Permutation
>>> Permutation([[3, 2], [0, 1]]).size
4

See also

cardinality, length, order, rank

support()

Return the elements in permutation, P, for which P[i] != i.

Examples

>>> from ..combinatorics import Permutation
>>> p = Permutation([[3, 2], [0, 1], [4]])
>>> p.array_form
[1, 0, 3, 2, 4]
>>> p.support()
[0, 1, 2, 3]

transpositions()

Return the permutation decomposed into a list of transpositions.

It is always possible to express a permutation as the product of transpositions, see [1]

Examples

>>> from .permutations import Permutation
>>> p = Permutation([[1, 2, 3], [0, 4, 5, 6, 7]])
>>> t = p.transpositions()
>>> t
[(0, 7), (0, 6), (0, 5), (0, 4), (1, 3), (1, 2)]
>>> print(''.join(str(c) for c in t))
(0, 7)(0, 6)(0, 5)(0, 4)(1, 3)(1, 2)
>>> Permutation.rmul(*[Permutation([ti], size=p.size) for ti in t]) == p
True

References

1. http://en.wikipedia.org/wiki/Transposition_%28mathematics%29#Properties

classmethod unrank_lex(size, rank)

Lexicographic permutation unranking.

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> a = Permutation.unrank_lex(5, 10)
>>> a.rank()
10
>>> a
Permutation([0, 2, 4, 1, 3])

See also

rank, next_lex

classmethod unrank_nonlex(n, r)

This is a linear time unranking algorithm that does not respect lexicographic order [3].

Examples

>>> from .permutations import Permutation
>>> Permutation.print_cyclic = False
>>> Permutation.unrank_nonlex(4, 5)
Permutation([2, 0, 3, 1])
>>> Permutation.unrank_nonlex(4, -1)
Permutation([0, 1, 2, 3])

See also

next_nonlex, rank_nonlex

classmethod unrank_trotterjohnson(size, rank)

Trotter Johnson permutation unranking. See [4] section 2.4.

Examples

>>> from .permutations import Permutation
>>> Permutation.unrank_trotterjohnson(5, 10)
Permutation([0, 3, 1, 2, 4])

See also

rank_trotterjohnson, next_trotterjohnson

modelparameters.sympy.combinatorics.polyhedron module

class modelparameters.sympy.combinatorics.polyhedron.Polyhedron(corners, faces=[], pgroup=[])

Bases: Basic

Represents the polyhedral symmetry group (PSG).

The PSG is one of the symmetry groups of the Platonic solids. There are three polyhedral groups: the tetrahedral group of order 12, the octahedral group of order 24, and the icosahedral group of order 60.

All doctests have been given in the docstring of the constructor of the object.

References

http://mathworld.wolfram.com/PolyhedralGroup.html

property array_form

Return the indices of the corners.

The indices are given relative to the original position of corners.

Examples

>>> from ..combinatorics import Permutation, Cycle
>>> from .polyhedron import tetrahedron
>>> tetrahedron.array_form
[0, 1, 2, 3]

>>> tetrahedron.rotate(0)
>>> tetrahedron.array_form
[0, 2, 3, 1]
>>> tetrahedron.pgroup[0].array_form
[0, 2, 3, 1]

See also

corners, cyclic_form

property corners

Get the corners of the Polyhedron.

The method vertices is an alias for corners.

Examples

>>> from ..combinatorics import Polyhedron
>>> from ..abc import a, b, c, d
>>> p = Polyhedron(list('abcd'))
>>> p.corners == p.vertices == (a, b, c, d)
True

See also

array_form, cyclic_form

property cyclic_form

Return the indices of the corners in cyclic notation.

The indices are given relative to the original position of corners.

See also

corners, array_form

default_assumptions = {}

property edges

Given the faces of the polyhedra we can get the edges.

Examples

>>> from ..combinatorics import Polyhedron
>>> from ..abc import a, b, c
>>> corners = (a, b, c)
>>> faces = [(0, 1, 2)]
>>> Polyhedron(corners, faces).edges
{(0, 1), (0, 2), (1, 2)}

property faces

Get the faces of the Polyhedron.

property pgroup

Get the permutations of the Polyhedron.

reset()

Return corners to their original positions.

Examples

>>> from .polyhedron import tetrahedron as T
>>> T.corners
(0, 1, 2, 3)
>>> T.rotate(0)
>>> T.corners
(0, 2, 3, 1)
>>> T.reset()
>>> T.corners
(0, 1, 2, 3)

rotate(perm)

Apply a permutation to the polyhedron in place. The permutation may be given as a Permutation instance or an integer indicating which permutation from pgroup of the Polyhedron should be applied.

This is an operation that is analogous to rotation about an axis by a fixed increment.

Notes

When a Permutation is applied, no check is done to see if that is a valid permutation for the Polyhedron. For example, a cube could be given a permutation which effectively swaps only 2 vertices. A valid permutation (that rotates the object in a physical way) will be obtained if one only uses permutations from the pgroup of the Polyhedron. On the other hand, allowing arbitrary rotations (applications of permutations) gives a way to follow named elements rather than indices since Polyhedron allows vertices to be named while Permutation works only with indices.

Examples

>>> from ..combinatorics import Polyhedron, Permutation
>>> from .polyhedron import cube
>>> cube.corners
(0, 1, 2, 3, 4, 5, 6, 7)
>>> cube.rotate(0)
>>> cube.corners
(1, 2, 3, 0, 5, 6, 7, 4)

A non-physical “rotation” that is not prohibited by this method:

>>> cube.reset()
>>> cube.rotate(Permutation([[1, 2]], size=8))
>>> cube.corners
(0, 2, 1, 3, 4, 5, 6, 7)

Polyhedron can be used to follow elements of set that are identified by letters instead of integers:

>>> shadow = h5 = Polyhedron(list('abcde'))
>>> p = Permutation([3, 0, 1, 2, 4])
>>> h5.rotate(p)
>>> h5.corners
(d, a, b, c, e)
>>> _ == shadow.corners
True
>>> copy = h5.copy()
>>> h5.rotate(p)
>>> h5.corners == copy.corners
False

property size

Get the number of corners of the Polyhedron.

property vertices

Get the corners of the Polyhedron.

The method vertices is an alias for corners.

Examples

>>> from ..combinatorics import Polyhedron
>>> from ..abc import a, b, c, d
>>> p = Polyhedron(list('abcd'))
>>> p.corners == p.vertices == (a, b, c, d)
True

See also

array_form, cyclic_form

modelparameters.sympy.combinatorics.prufer module

class modelparameters.sympy.combinatorics.prufer.Prufer(*args, **kw_args)

Bases: Basic

The Prufer correspondence is an algorithm that describes the bijection between labeled trees and the Prufer code. A Prufer code of a labeled tree is unique up to isomorphism and has a length of n - 2.

Prufer sequences were first used by Heinz Prufer to give a proof of Cayley’s formula.

References

[1]

http://mathworld.wolfram.com/LabeledTree.html

default_assumptions = {}

static edges(*runs)

Return a list of edges and the number of nodes from the given runs that connect nodes in an integer-labelled tree.

All node numbers will be shifted so that the minimum node is 0. It is not a problem if edges are repeated in the runs; only unique edges are returned. There is no assumption made about what the range of the node labels should be, but all nodes from the smallest through the largest must be present.

Examples

>>> from .prufer import Prufer
>>> Prufer.edges([1, 2, 3], [2, 4, 5]) # a T
([[0, 1], [1, 2], [1, 3], [3, 4]], 5)

Duplicate edges are removed:

>>> Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) # a K
([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)

next(delta=1)

Generates the Prufer sequence that is delta beyond the current one.

Examples

>>> from .prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> b = a.next(1) # == a.next()
>>> b.tree_repr
[[0, 2], [0, 1], [1, 3]]
>>> b.rank
1

See also

prufer_rank, rank, prev, size

property nodes

Returns the number of nodes in the tree.

Examples

>>> from .prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).nodes
6
>>> Prufer([1, 0, 0]).nodes
5

prev(delta=1)

Generates the Prufer sequence that is -delta before the current one.

Examples

>>> from .prufer import Prufer
>>> a = Prufer([[0, 1], [1, 2], [2, 3], [1, 4]])
>>> a.rank
36
>>> b = a.prev()
>>> b
Prufer([1, 2, 0])
>>> b.rank
35

See also

prufer_rank, rank, next, size

prufer_rank()

Computes the rank of a Prufer sequence.

Examples

>>> from .prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> a.prufer_rank()
0

See also

rank, next, prev, size

property prufer_repr

Returns Prufer sequence for the Prufer object.

This sequence is found by removing the highest numbered vertex, recording the node it was attached to, and continuing until only two vertices remain. The Prufer sequence is the list of recorded nodes.

Examples

>>> from .prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).prufer_repr
[3, 3, 3, 4]
>>> Prufer([1, 0, 0]).prufer_repr
[1, 0, 0]

See also

to_prufer

property rank

Returns the rank of the Prufer sequence.

Examples

>>> from .prufer import Prufer
>>> p = Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]])
>>> p.rank
778
>>> p.next(1).rank
779
>>> p.prev().rank
777

See also

prufer_rank, next, prev, size

property size

Return the number of possible trees of this Prufer object.

Examples

>>> from .prufer import Prufer
>>> Prufer([0]*4).size == Prufer([6]*4).size == 1296
True

See also

prufer_rank, rank, next, prev

static to_prufer(tree, n)

Return the Prufer sequence for a tree given as a list of edges where n is the number of nodes in the tree.

Examples

>>> from .prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> a.prufer_repr
[0, 0]
>>> Prufer.to_prufer([[0, 1], [0, 2], [0, 3]], 4)
[0, 0]

See also

prufer_repr

returns Prufer sequence of a Prufer object.

static to_tree(prufer)

Return the tree (as a list of edges) of the given Prufer sequence.

Examples

>>> from .prufer import Prufer
>>> a = Prufer([0, 2], 4)
>>> a.tree_repr
[[0, 1], [0, 2], [2, 3]]
>>> Prufer.to_tree([0, 2])
[[0, 1], [0, 2], [2, 3]]

References

• https://hamberg.no/erlend/posts/2010-11-06-prufer-sequence-compact-tree-representation.html

See also

tree_repr

returns tree representation of a Prufer object.

property tree_repr

Returns the tree representation of the Prufer object.

Examples

>>> from .prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).tree_repr
[[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]
>>> Prufer([1, 0, 0]).tree_repr
[[1, 2], [0, 1], [0, 3], [0, 4]]

See also

to_tree

classmethod unrank(rank, n)

Finds the unranked Prufer sequence.

Examples

>>> from .prufer import Prufer
>>> Prufer.unrank(0, 4)
Prufer([0, 0])

modelparameters.sympy.combinatorics.subsets module

class modelparameters.sympy.combinatorics.subsets.Subset(subset, superset)

Bases: Basic

Represents a basic subset object.

We generate subsets using essentially two techniques, binary enumeration and lexicographic enumeration. The Subset class takes two arguments, the first one describes the initial subset to consider and the second describes the superset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
['b']
>>> a.prev_binary().subset
['c']

classmethod bitlist_from_subset(subset, superset)

Gets the bitlist corresponding to a subset.

Examples

>>> from .subsets import Subset
>>> Subset.bitlist_from_subset(['c', 'd'], ['a', 'b', 'c', 'd'])
'0011'

See also

subset_from_bitlist

property cardinality

Returns the number of all possible subsets.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.cardinality
16

See also

subset, superset, size, superset_size

default_assumptions = {}

iterate_binary(k)

This is a helper function. It iterates over the binary subsets by k steps. This variable can be both positive or negative.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.iterate_binary(-2).subset
['d']
>>> a = Subset(['a', 'b', 'c'], ['a', 'b', 'c', 'd'])
>>> a.iterate_binary(2).subset
[]

See also

next_binary, prev_binary

iterate_graycode(k)

Helper function used for prev_gray and next_gray. It performs k step overs to get the respective Gray codes.

Examples

>>> from .subsets import Subset
>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.iterate_graycode(3).subset
[1, 4]
>>> a.iterate_graycode(-2).subset
[1, 2, 4]

See also

next_gray, prev_gray

next_binary()

Generates the next binary ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
['b']
>>> a = Subset(['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_binary().subset
[]

See also

prev_binary, iterate_binary

next_gray()

Generates the next Gray code ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset([1, 2, 3], [1, 2, 3, 4])
>>> a.next_gray().subset
[1, 3]

See also

iterate_graycode, prev_gray

next_lexicographic()

Generates the next lexicographically ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
['d']
>>> a = Subset(['d'], ['a', 'b', 'c', 'd'])
>>> a.next_lexicographic().subset
[]

See also

prev_lexicographic

prev_binary()

Generates the previous binary ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.prev_binary().subset
['a', 'b', 'c', 'd']
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.prev_binary().subset
['c']

See also

next_binary, iterate_binary

prev_gray()

Generates the previous Gray code ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset([2, 3, 4], [1, 2, 3, 4, 5])
>>> a.prev_gray().subset
[2, 3, 4, 5]

See also

iterate_graycode, next_gray

prev_lexicographic()

Generates the previous lexicographically ordered subset.

Examples

>>> from .subsets import Subset
>>> a = Subset([], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['d']
>>> a = Subset(['c','d'], ['a', 'b', 'c', 'd'])
>>> a.prev_lexicographic().subset
['c']

See also

next_lexicographic

property rank_binary

Computes the binary ordered rank.

Examples

>>> from .subsets import Subset
>>> a = Subset([], ['a','b','c','d'])
>>> a.rank_binary
0
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.rank_binary
3

See also

iterate_binary, unrank_binary

property rank_gray

Computes the Gray code ranking of the subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c','d'], ['a','b','c','d'])
>>> a.rank_gray
2
>>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
>>> a.rank_gray
27

See also

iterate_graycode, unrank_gray

property rank_lexicographic

Computes the lexicographic ranking of the subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.rank_lexicographic
14
>>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
>>> a.rank_lexicographic
43

property size

Gets the size of the subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.size
2

See also

subset, superset, superset_size, cardinality

property subset

Gets the subset represented by the current instance.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.subset
['c', 'd']

See also

superset, size, superset_size, cardinality

classmethod subset_from_bitlist(super_set, bitlist)

Gets the subset defined by the bitlist.

Examples

>>> from .subsets import Subset
>>> Subset.subset_from_bitlist(['a', 'b', 'c', 'd'], '0011').subset
['c', 'd']

See also

bitlist_from_subset

classmethod subset_indices(subset, superset)

Return indices of subset in superset in a list; the list is empty if all elements of subset are not in superset.

Examples

>>> from ..combinatorics import Subset
>>> superset = [1, 3, 2, 5, 4]
>>> Subset.subset_indices([3, 2, 1], superset)
[1, 2, 0]
>>> Subset.subset_indices([1, 6], superset)
[]
>>> Subset.subset_indices([], superset)
[]

property superset

Gets the superset of the subset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset
['a', 'b', 'c', 'd']

See also

subset, size, superset_size, cardinality

property superset_size

Returns the size of the superset.

Examples

>>> from .subsets import Subset
>>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
>>> a.superset_size
4

See also

subset, superset, size, cardinality

classmethod unrank_binary(rank, superset)

Gets the binary ordered subset of the specified rank.

Examples

>>> from .subsets import Subset
>>> Subset.unrank_binary(4, ['a', 'b', 'c', 'd']).subset
['b']

See also

iterate_binary, rank_binary

classmethod unrank_gray(rank, superset)

Gets the Gray code ordered subset of the specified rank.

Examples

>>> from .subsets import Subset
>>> Subset.unrank_gray(4, ['a', 'b', 'c']).subset
['a', 'b']
>>> Subset.unrank_gray(0, ['a', 'b', 'c']).subset
[]

See also

iterate_graycode, rank_gray

modelparameters.sympy.combinatorics.subsets.ksubsets(superset, k)

Finds the subsets of size k in lexicographic order.

This uses the itertools generator.

Examples

>>> from .subsets import ksubsets
>>> list(ksubsets([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]
>>> list(ksubsets([1, 2, 3, 4, 5], 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4),     (2, 5), (3, 4), (3, 5), (4, 5)]

See also

class

Subset

modelparameters.sympy.combinatorics.tensor_can module

modelparameters.sympy.combinatorics.tensor_can.bsgs_direct_product(base1, gens1, base2, gens2, signed=True)

direct product of two BSGS

base1 base of the first BSGS.

gens1 strong generating sequence of the first BSGS.

base2, gens2 similarly for the second BSGS.

signed flag for signed permutations.

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import (get_symmetric_group_sgs, bsgs_direct_product)
>>> Permutation.print_cyclic = True
>>> base1, gens1 = get_symmetric_group_sgs(1)
>>> base2, gens2 = get_symmetric_group_sgs(2)
>>> bsgs_direct_product(base1, gens1, base2, gens2)
([1], [(4)(1 2)])

modelparameters.sympy.combinatorics.tensor_can.canonical_free(base, gens, g, num_free)

canonicalization of a tensor with respect to free indices choosing the minimum with respect to lexicographical ordering in the free indices

base, gens BSGS for slot permutation group g permutation representing the tensor num_free number of free indices The indices must be ordered with first the free indices

see explanation in double_coset_can_rep The algorithm is a variation of the one given in [2].

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import canonical_free
>>> gens = [[1, 0, 2, 3, 5, 4], [2, 3, 0, 1, 4, 5],[0, 1, 3, 2, 5, 4]]
>>> gens = [Permutation(h) for h in gens]
>>> base = [0, 2]
>>> g = Permutation([2, 1, 0, 3, 4, 5])
>>> canonical_free(base, gens, g, 4)
[0, 3, 1, 2, 5, 4]

Consider the product of Riemann tensors T = R^{a}_{d0}^{d1,d2}*R_{d2,d1}^{d0,b} The order of the indices is [a, b, d0, -d0, d1, -d1, d2, -d2] The permutation corresponding to the tensor is g = [0, 3, 4, 6, 7, 5, 2, 1, 8, 9]

In particular a is position 0, b is in position 9. Use the slot symmetries to get T is a form which is the minimal in lexicographic order in the free indices a and b, e.g. -R^{a}_{d0}^{d1,d2}*R^{b,d0}_{d2,d1} corresponding to [0, 3, 4, 6, 1, 2, 7, 5, 9, 8]

>>> from .tensor_can import riemann_bsgs, tensor_gens
>>> base, gens = riemann_bsgs
>>> size, sbase, sgens = tensor_gens(base, gens, [[], []], 0)
>>> g = Permutation([0, 3, 4, 6, 7, 5, 2, 1, 8, 9])
>>> canonical_free(sbase, [Permutation(h) for h in sgens], g, 2)
[0, 3, 4, 6, 1, 2, 7, 5, 9, 8]

modelparameters.sympy.combinatorics.tensor_can.canonicalize(g, dummies, msym, *v)

canonicalize tensor formed by tensors

Parameters:

• g (permutation representing the tensor) –

• dummies (list representing the dummy indices) – it can be a list of dummy indices of the same type or a list of lists of dummy indices, one list for each type of index; the dummy indices must come after the free indices, and put in order contravariant, covariant [d0, -d0, d1,-d1,…]

• msym (symmetry of the metric(s)) – it can be an integer or a list; in the first case it is the symmetry of the dummy index metric; in the second case it is the list of the symmetries of the index metric for each type

• v (list, (base_i, gens_i, n_i, sym_i) for tensors of type i) –

• base_i (BSGS for tensors of this type.) – The BSGS should have minimal base under lexicographic ordering; if not, an attempt is made do get the minimal BSGS; in case of failure, canonicalize_naive is used, which is much slower.

• gens_i (BSGS for tensors of this type.) – The BSGS should have minimal base under lexicographic ordering; if not, an attempt is made do get the minimal BSGS; in case of failure, canonicalize_naive is used, which is much slower.

• n_i (number of tensors of type i.) –

• sym_i (symmetry under exchange of component tensors of type i.) –

  Both for msym and sym_i the cases are

  • None no symmetry

  • 0 commuting

  • 1 anticommuting

Returns:

• 0 if the tensor is zero, else return the array form of

• the permutation representing the canonical form of the tensor.

• Algorithm

• =========

• First one uses canonical_free to get the minimum tensor under

• lexicographic order, using only the slot symmetries.

• If the component tensors have not minimal BSGS, it is attempted

• to find it; if the attempt fails canonicalize_naive

• is used instead.

• Compute the residual slot symmetry keeping fixed the free indices

• using tensor_gens(base, gens, list_free_indices, sym).

• Reduce the problem eliminating the free indices.

• Then use double_coset_can_rep and lift back the result reintroducing

• the free indices.

Examples

one type of index with commuting metric;

A_{a b} and B_{a b} antisymmetric and commuting

T = A_{d0 d1} * B^{d0}{}_{d2} * B^{d2 d1}

ord = [d0,-d0,d1,-d1,d2,-d2] order of the indices

g = [1, 3, 0, 5, 4, 2, 6, 7]

T_c = 0

>>> from .tensor_can import get_symmetric_group_sgs, canonicalize, bsgs_direct_product
>>> from ..combinatorics import Permutation
>>> base2a, gens2a = get_symmetric_group_sgs(2, 1)
>>> t0 = (base2a, gens2a, 1, 0)
>>> t1 = (base2a, gens2a, 2, 0)
>>> g = Permutation([1, 3, 0, 5, 4, 2, 6, 7])
>>> canonicalize(g, range(6), 0, t0, t1)
0

same as above, but with B_{a b} anticommuting

T_c = -A^{d0 d1} * B_{d0}{}^{d2} * B_{d1 d2}

can = [0,2,1,4,3,5,7,6]

>>> t1 = (base2a, gens2a, 2, 1)
>>> canonicalize(g, range(6), 0, t0, t1)
[0, 2, 1, 4, 3, 5, 7, 6]

two types of indices [a,b,c,d,e,f] and [m,n], in this order, both with commuting metric

f^{a b c} antisymmetric, commuting

A_{m a} no symmetry, commuting

T = f^c{}_{d a} * f^f{}_{e b} * A_m{}^d * A^{m b} * A_n{}^a * A^{n e}

ord = [c,f,a,-a,b,-b,d,-d,e,-e,m,-m,n,-n]

g = [0,7,3, 1,9,5, 11,6, 10,4, 13,2, 12,8, 14,15]

The canonical tensor is T_c = -f^{c a b} * f^{f d e} * A^m{}_a * A_{m d} * A^n{}_b * A_{n e}

can = [0,2,4, 1,6,8, 10,3, 11,7, 12,5, 13,9, 15,14]

>>> base_f, gens_f = get_symmetric_group_sgs(3, 1)
>>> base1, gens1 = get_symmetric_group_sgs(1)
>>> base_A, gens_A = bsgs_direct_product(base1, gens1, base1, gens1)
>>> t0 = (base_f, gens_f, 2, 0)
>>> t1 = (base_A, gens_A, 4, 0)
>>> dummies = [range(2, 10), range(10, 14)]
>>> g = Permutation([0, 7, 3, 1, 9, 5, 11, 6, 10, 4, 13, 2, 12, 8, 14, 15])
>>> canonicalize(g, dummies, [0, 0], t0, t1)
[0, 2, 4, 1, 6, 8, 10, 3, 11, 7, 12, 5, 13, 9, 15, 14]

modelparameters.sympy.combinatorics.tensor_can.double_coset_can_rep(dummies, sym, b_S, sgens, S_transversals, g)

Butler-Portugal algorithm for tensor canonicalization with dummy indices

dummies

list of lists of dummy indices, one list for each type of index; the dummy indices are put in order contravariant, covariant [d0, -d0, d1, -d1, …].

sym

list of the symmetries of the index metric for each type.

possible symmetries of the metrics

• 0 symmetric

• 1 antisymmetric

• None no symmetry

b_S

base of a minimal slot symmetry BSGS.

sgens

generators of the slot symmetry BSGS.

S_transversals

transversals for the slot BSGS.

g

permutation representing the tensor.

Return 0 if the tensor is zero, else return the array form of the permutation representing the canonical form of the tensor.

A tensor with dummy indices can be represented in a number of equivalent ways which typically grows exponentially with the number of indices. To be able to establish if two tensors with many indices are equal becomes computationally very slow in absence of an efficient algorithm.

The Butler-Portugal algorithm [3] is an efficient algorithm to put tensors in canonical form, solving the above problem.

Portugal observed that a tensor can be represented by a permutation, and that the class of tensors equivalent to it under slot and dummy symmetries is equivalent to the double coset D*g*S (Note: in this documentation we use the conventions for multiplication of permutations p, q with (p*q)(i) = p[q[i]] which is opposite to the one used in the Permutation class)

Using the algorithm by Butler to find a representative of the double coset one can find a canonical form for the tensor.

To see this correspondence, let g be a permutation in array form; a tensor with indices ind (the indices including both the contravariant and the covariant ones) can be written as

t = T(ind[g[0],…, ind[g[n-1]]),

where n= len(ind); g has size n + 2, the last two indices for the sign of the tensor (trick introduced in [4]).

A slot symmetry transformation s is a permutation acting on the slots t -> T(ind[(g*s)[0]],…, ind[(g*s)[n-1]])

A dummy symmetry transformation acts on ind t -> T(ind[(d*g)[0]],…, ind[(d*g)[n-1]])

Being interested only in the transformations of the tensor under these symmetries, one can represent the tensor by g, which transforms as

g -> d*g*s, so it belongs to the coset D*g*S.

Let us explain the conventions by an example.

Given a tensor T^{d3 d2 d1}{}_{d1 d2 d3} with the slot symmetries

T^{a0 a1 a2 a3 a4 a5} = -T^{a2 a1 a0 a3 a4 a5}

T^{a0 a1 a2 a3 a4 a5} = -T^{a4 a1 a2 a3 a0 a5}

and symmetric metric, find the tensor equivalent to it which is the lowest under the ordering of indices: lexicographic ordering d1, d2, d3 then and contravariant index before covariant index; that is the canonical form of the tensor.

The canonical form is -T^{d1 d2 d3}{}_{d1 d2 d3} obtained using T^{a0 a1 a2 a3 a4 a5} = -T^{a2 a1 a0 a3 a4 a5}.

To convert this problem in the input for this function, use the following labelling of the index names (- for covariant for short) d1, -d1, d2, -d2, d3, -d3

T^{d3 d2 d1}{}_{d1 d2 d3} corresponds to g = [4, 2, 0, 1, 3, 5, 6, 7] where the last two indices are for the sign

sgens = [Permutation(0, 2)(6, 7), Permutation(0, 4)(6, 7)]

sgens[0] is the slot symmetry -(0, 2) T^{a0 a1 a2 a3 a4 a5} = -T^{a2 a1 a0 a3 a4 a5}

sgens[1] is the slot symmetry -(0, 4) T^{a0 a1 a2 a3 a4 a5} = -T^{a4 a1 a2 a3 a0 a5}

The dummy symmetry group D is generated by the strong base generators [(0, 1), (2, 3), (4, 5), (0, 1)(2, 3),(2, 3)(4, 5)]

The dummy symmetry acts from the left d = [1, 0, 2, 3, 4, 5, 6, 7] exchange d1 -> -d1 T^{d3 d2 d1}{}_{d1 d2 d3} == T^{d3 d2}{}_{d1}{}^{d1}{}_{d2 d3}

g=[4, 2, 0, 1, 3, 5, 6, 7] -> [4, 2, 1, 0, 3, 5, 6, 7] = _af_rmul(d, g) which differs from _af_rmul(g, d).

The slot symmetry acts from the right s = [2, 1, 0, 3, 4, 5, 7, 6] exchanges slots 0 and 2 and changes sign T^{d3 d2 d1}{}_{d1 d2 d3} == -T^{d1 d2 d3}{}_{d1 d2 d3}

g=[4,2,0,1,3,5,6,7] -> [0, 2, 4, 1, 3, 5, 7, 6] = _af_rmul(g, s)

Example in which the tensor is zero, same slot symmetries as above: T^{d3}{}_{d1,d2}{}^{d1}{}_{d3}{}^{d2}

= -T^{d3}{}_{d1,d3}{}^{d1}{}_{d2}{}^{d2} under slot symmetry -(2,4);

= T_{d3 d1}{}^{d3}{}^{d1}{}_{d2}{}^{d2} under slot symmetry -(0,2);

= T^{d3}{}_{d1 d3}{}^{d1}{}_{d2}{}^{d2} symmetric metric;

= 0 since two of these lines have tensors differ only for the sign.

The double coset D*g*S consists of permutations h = d*g*s corresponding to equivalent tensors; if there are two h which are the same apart from the sign, return zero; otherwise choose as representative the tensor with indices ordered lexicographically according to [d1, -d1, d2, -d2, d3, -d3] that is rep = min(D*g*S) = min([d*g*s for d in D for s in S])

The indices are fixed one by one; first choose the lowest index for slot 0, then the lowest remaining index for slot 1, etc. Doing this one obtains a chain of stabilizers

S -> S_{b0} -> S_{b0,b1} -> … and D -> D_{p0} -> D_{p0,p1} -> …

where [b0, b1, …] = range(b) is a base of the symmetric group; the strong base b_S of S is an ordered sublist of it; therefore it is sufficient to compute once the strong base generators of S using the Schreier-Sims algorithm; the stabilizers of the strong base generators are the strong base generators of the stabilizer subgroup.

dbase = [p0, p1, …] is not in general in lexicographic order, so that one must recompute the strong base generators each time; however this is trivial, there is no need to use the Schreier-Sims algorithm for D.

The algorithm keeps a TAB of elements (s_i, d_i, h_i) where h_i = d_i*g*s_i satisfying h_i[j] = p_j for 0 <= j < i starting from s_0 = id, d_0 = id, h_0 = g.

The equations h_0[0] = p_0, h_1[1] = p_1,… are solved in this order, choosing each time the lowest possible value of p_i

For j < i d_i*g*s_i*S_{b_0,…,b_{i-1}}*b_j = D_{p_0,…,p_{i-1}}*p_j so that for dx in D_{p_0,…,p_{i-1}} and sx in S_{base[0],…,base[i-1]} one has dx*d_i*g*s_i*sx*b_j = p_j

Search for dx, sx such that this equation holds for j = i; it can be written as s_i*sx*b_j = J, dx*d_i*g*J = p_j sx*b_j = s_i**-1*J; sx = trace(s_i**-1, S_{b_0,…,b_{i-1}}) dx**-1*p_j = d_i*g*J; dx = trace(d_i*g*J, D_{p_0,…,p_{i-1}})

s_{i+1} = s_i*trace(s_i**-1*J, S_{b_0,…,b_{i-1}}) d_{i+1} = trace(d_i*g*J, D_{p_0,…,p_{i-1}})**-1*d_i h_{i+1}*b_i = d_{i+1}*g*s_{i+1}*b_i = p_i

h_n*b_j = p_j for all j, so that h_n is the solution.

Add the found (s, d, h) to TAB1.

At the end of the iteration sort TAB1 with respect to the h; if there are two consecutive h in TAB1 which differ only for the sign, the tensor is zero, so return 0; if there are two consecutive h which are equal, keep only one.

Then stabilize the slot generators under i and the dummy generators under p_i.

Assign TAB = TAB1 at the end of the iteration step.

At the end TAB contains a unique (s, d, h), since all the slots of the tensor h have been fixed to have the minimum value according to the symmetries. The algorithm returns h.

It is important that the slot BSGS has lexicographic minimal base, otherwise there is an i which does not belong to the slot base for which p_i is fixed by the dummy symmetry only, while i is not invariant from the slot stabilizer, so p_i is not in general the minimal value.

This algorithm differs slightly from the original algorithm [3]:

the canonical form is minimal lexicographically, and the BSGS has minimal base under lexicographic order. Equal tensors h are eliminated from TAB.

Examples

>>> from .permutations import Permutation
>>> from .perm_groups import PermutationGroup
>>> from .tensor_can import double_coset_can_rep, get_transversals
>>> gens = [Permutation(x) for x in [[2, 1, 0, 3, 4, 5, 7, 6], [4, 1, 2, 3, 0, 5, 7, 6]]]
>>> base = [0, 2]
>>> g = Permutation([4, 2, 0, 1, 3, 5, 6, 7])
>>> transversals = get_transversals(base, gens)
>>> double_coset_can_rep([list(range(6))], [0], base, gens, transversals, g)
[0, 1, 2, 3, 4, 5, 7, 6]

>>> g = Permutation([4, 1, 3, 0, 5, 2, 6, 7])
>>> double_coset_can_rep([list(range(6))], [0], base, gens, transversals, g)
0

modelparameters.sympy.combinatorics.tensor_can.dummy_sgs(dummies, sym, n)

Return the strong generators for dummy indices

Parameters:

• dummies (list of dummy indices) – dummies[2k], dummies[2k+1] are paired indices

• sym (symmetry under interchange of contracted dummies:) –

  • None no symmetry

  • 0 commuting

  • 1 anticommuting

• n (number of indices) –

• positions (in base form the dummy indices are always in consecutive) –

Examples

>>> from .tensor_can import dummy_sgs
>>> dummy_sgs(range(2, 8), 0, 8)
[[0, 1, 3, 2, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 5, 4, 6, 7, 8, 9],
 [0, 1, 2, 3, 4, 5, 7, 6, 8, 9], [0, 1, 4, 5, 2, 3, 6, 7, 8, 9],
 [0, 1, 2, 3, 6, 7, 4, 5, 8, 9]]

modelparameters.sympy.combinatorics.tensor_can.gens_products(*v)

Returns size, res_base, res_gens BSGS for n tensors of different types

v is a sequence of (base_i, gens_i, free_i, sym_i) where base_i, gens_i BSGS of tensor of type i free_i list of the fixed slots for each of the tensors

of type i; if there are n_i tensors of type i and none of them have fixed slots, free = [[]]*n_i

sym 0 (1) if the tensors of type i (anti)commute among themselves

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import get_symmetric_group_sgs, gens_products
>>> Permutation.print_cyclic = True
>>> base, gens = get_symmetric_group_sgs(2)
>>> gens_products((base, gens, [[], []], 0))
(6, [0, 2], [(5)(0 1), (5)(2 3), (5)(0 2)(1 3)])
>>> gens_products((base, gens, [[1], []], 0))
(6, [2], [(5)(2 3)])

modelparameters.sympy.combinatorics.tensor_can.get_minimal_bsgs(base, gens)

Compute a minimal GSGS

base, gens BSGS

If base, gens is a minimal BSGS return it; else return a minimal BSGS if it fails in finding one, it returns None

TODO: use baseswap in the case in which if it fails in finding a minimal BSGS

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import get_minimal_bsgs
>>> Permutation.print_cyclic = True
>>> riemann_bsgs1 = ([2, 0], ([Permutation(5)(0, 1)(4, 5), Permutation(5)(0, 2)(1, 3)]))
>>> get_minimal_bsgs(*riemann_bsgs1)
([0, 2], [(0 1)(4 5), (5)(0 2)(1 3), (2 3)(4 5)])

modelparameters.sympy.combinatorics.tensor_can.get_symmetric_group_sgs(n, antisym=False)

Return base, gens of the minimal BSGS for (anti)symmetric tensor

n rank of the tensor

antisym = False symmetric tensor antisym = True antisymmetric tensor

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import get_symmetric_group_sgs
>>> Permutation.print_cyclic = True
>>> get_symmetric_group_sgs(3)
([0, 1], [(4)(0 1), (4)(1 2)])

modelparameters.sympy.combinatorics.tensor_can.get_transversals(base, gens)

Return transversals for the group with BSGS base, gens

modelparameters.sympy.combinatorics.tensor_can.perm_af_direct_product(gens1, gens2, signed=True)

direct products of the generators gens1 and gens2

Examples

>>> from .tensor_can import perm_af_direct_product
>>> gens1 = [[1, 0, 2, 3], [0, 1, 3, 2]]
>>> gens2 = [[1, 0]]
>>> perm_af_direct_product(gens1, gens2, False)
[[1, 0, 2, 3, 4, 5], [0, 1, 3, 2, 4, 5], [0, 1, 2, 3, 5, 4]]
>>> gens1 = [[1, 0, 2, 3, 5, 4], [0, 1, 3, 2, 4, 5]]
>>> gens2 = [[1, 0, 2, 3]]
>>> perm_af_direct_product(gens1, gens2, True)
[[1, 0, 2, 3, 4, 5, 7, 6], [0, 1, 3, 2, 4, 5, 6, 7], [0, 1, 2, 3, 5, 4, 6, 7]]

modelparameters.sympy.combinatorics.tensor_can.tensor_gens(base, gens, list_free_indices, sym=0)

Returns size, res_base, res_gens BSGS for n tensors of the same type

base, gens BSGS for tensors of this type list_free_indices list of the slots occupied by fixed indices

for each of the tensors

sym symmetry under commutation of two tensors sym None no symmetry sym 0 commuting sym 1 anticommuting

Examples

>>> from ..combinatorics import Permutation
>>> from .tensor_can import tensor_gens, get_symmetric_group_sgs
>>> Permutation.print_cyclic = True

two symmetric tensors with 3 indices without free indices

>>> base, gens = get_symmetric_group_sgs(3)
>>> tensor_gens(base, gens, [[], []])
(8, [0, 1, 3, 4], [(7)(0 1), (7)(1 2), (7)(3 4), (7)(4 5), (7)(0 3)(1 4)(2 5)])

two symmetric tensors with 3 indices with free indices in slot 1 and 0

>>> tensor_gens(base, gens, [[1], [0]])
(8, [0, 4], [(7)(0 2), (7)(4 5)])

four symmetric tensors with 3 indices, two of which with free indices

modelparameters.sympy.combinatorics.tensor_can.transversal2coset(size, base, transversal)

modelparameters.sympy.combinatorics.testutil module

modelparameters.sympy.combinatorics.testutil.canonicalize_naive(g, dummies, sym, *v)

Canonicalize tensor formed by tensors of the different types

g permutation representing the tensor dummies list of dummy indices msym symmetry of the metric

v is a list of (base_i, gens_i, n_i, sym_i) for tensors of type i base_i, gens_i BSGS for tensors of this type n_i number ot tensors of type i

sym_i symmetry under exchange of two component tensors of type i

None no symmetry 0 commuting 1 anticommuting

Return 0 if the tensor is zero, else return the array form of the permutation representing the canonical form of the tensor.

Examples

>>> from .testutil import canonicalize_naive
>>> from .tensor_can import get_symmetric_group_sgs
>>> from ..combinatorics import Permutation, PermutationGroup
>>> g = Permutation([1, 3, 2, 0, 4, 5])
>>> base2, gens2 = get_symmetric_group_sgs(2)
>>> canonicalize_naive(g, [2, 3], 0, (base2, gens2, 2, 0))
[0, 2, 1, 3, 4, 5]

modelparameters.sympy.combinatorics.testutil.graph_certificate(gr)

Return a certificate for the graph

gr adjacency list

The graph is assumed to be unoriented and without external lines.

Associate to each vertex of the graph a symmetric tensor with number of indices equal to the degree of the vertex; indices are contracted when they correspond to the same line of the graph. The canonical form of the tensor gives a certificate for the graph.

This is not an efficient algorithm to get the certificate of a graph.

Examples

>>> from .testutil import graph_certificate
>>> gr1 = {0:[1, 2, 3, 5], 1:[0, 2, 4], 2:[0, 1, 3, 4], 3:[0, 2, 4], 4:[1, 2, 3, 5], 5:[0, 4]}
>>> gr2 = {0:[1, 5], 1:[0, 2, 3, 4], 2:[1, 3, 5], 3:[1, 2, 4, 5], 4:[1, 3, 5], 5:[0, 2, 3, 4]}
>>> c1 = graph_certificate(gr1)
>>> c2 = graph_certificate(gr2)
>>> c1
[0, 2, 4, 6, 1, 8, 10, 12, 3, 14, 16, 18, 5, 9, 15, 7, 11, 17, 13, 19, 20, 21]
>>> c1 == c2
True

modelparameters.sympy.combinatorics.util module

Module contents