PermSpace and Perm

PermSpace

class PermSpace(iterable_or_length, n_elements=None, *, domain=None, fixed_map=None, degrees=None, is_combination=False, slice_=None, perm_type=None)

A space of permutations on a sequence.

Each item in a PermSpace is a Perm, i.e. a permutation. This is similar to itertools.permutations(), except it offers far, far more functionality. The permutations may be accessed by index number, the permutation space can have its range and domain specified, some items can be fixed, and more.

Here is the simplest possible PermSpace:

>>> perm_space = PermSpace(3)
<PermSpace: 0..2>
>>> perm_space[2]
<Perm: (1, 0, 2)>
>>> tuple(perm_space)
(<Perm: (0, 1, 2)>, <Perm: (0, 2, 1)>, <Perm: (1, 0, 2)>,
 <Perm: (1, 2, 0)>, <Perm: (2, 0, 1)>, <Perm: (2, 1, 0)>)

The members are Perm objects, which are sequence-like objects that have extra functionality. (See documentation of Perm for more info.)

The permutations are generated on-demand, not in advance. This means you can easily create something like PermSpace(1000), which has about 10**2500 permutations in it (a number that far exceeds the number of particles in the universe), in a fraction of a second. You can then fetch by index number any permutation of the 10**2500 permutations in a fraction of a second as well.

PermSpace allows the creation of various special kinds of permutation spaces. For example, you can specify an integer to n_elements to set a permutation length that’s smaller than the sequence length. (a.k.a. k-permutations.) This variation of a PermSpace is called “partial” and it’s one of 8 different variations, that are listed below.

• Rapplied (Range-applied): Having an arbitrary sequence as a range. To make one, pass your sequence as the first argument instead of the length.
• Dapplied (Domain-applied): Having an arbitrary sequence as a domain. To make one, pass a sequence into the domain argument.
• Recurrent: If you provide a sequence (making the space rapplied) and that sequence has repeating items, you’ve made a recurrent PermSpace. It’ll be shorter because all of the copies of same item will be considered the same item. (Though they will appear more than once, according to their count in the sequence.)
• Fixed: Having a specified number of indices always pointing at certain values, making the space smaller. To make one, pass a dict from each key to the value it should be fixed to as the argument fixed_map, like PermSpace('meow', fixed_map={0: 'm', 1: 'w'})
• Sliced: A perm space can be sliced like any Python sequence (except you can’t change the step.) To make one, use slice notation on an existing perm space, e.g. perm_space[56:100].
• Degreed: A perm space can be limited to perms of a certain degree. (A perm’s degree is the number of transformations it takes to make it.) To make one, pass into the degrees argument either a single degree (like 5) or a tuple of different degrees (like (1, 3, 7))
• Partial: A perm space can be partial, in which case not all elements are used in perms. E.g. you can have a perm space of a sequence of length 5 but with n_elements=3, so every perm will have only 3 items. (These are usually called k-permutations in math-land.) To make one, pass a number as the argument n_elements.
• Combination: If you pass in is_combination=True or use the subclass CombSpace, then you’ll have a space of combinations (Combs) instead of perms. Combs are like Perms except there’s no order to the elements. (They are always forced into canonical order.)
• Typed: If you pass in a perm subclass as perm_type, you’ll get a typed PermSpace, meaning that the perms will use the class you provide rather than the default Perm. This is useful when you want to provide extra functionality on top of Perm that’s specific to your use case.

Most of these variations can be used in conjuction with each other, but some cannot:

• A combination space can’t be dapplied, degreed, or fixed.
• A partial permutation space can’t be degreed.
• A recurrent permutation space must be rapplied and can’t be degreed.

For each of these variations, there’s a function to make a perm space have that variation and get rid of it. For example, if you want to make a normal perm space be degreed, call get_degreed() on it with the desired degrees. If you want to make a degreed perm space non-degreed, access its undegreed property. The same is true for all other variations.

A perm space that has none of these variations is called pure.

coerce_perm(perm)

Coerce a sequence to be a permutation of this space.

index(perm)

Get the index number of permutation perm in this space.

For example:

>>> perm_space = PermSpace(3)
>>> perm_space.index((2, 1, 0))
5
>>> perm_space[5]
<Perm: (2, 1, 0)>

length

The PermSpace‘s length, i.e. the number of permutations in it.

This is also accessible as len(perm_space), but since CPython doesn’t support very large length numbers, it’s best to access it through perm_space.length.

Methods and properties for adding a variation to a perm space: (A new perm space is returned, the original one does not get modified)

get_rapplied(sequence)

Get a rapplied version of this PermSpace that has a range of sequence.

get_dapplied(domain)

Get a dapplied version of this PermSpace that has a domain of domain.

(There’s no get_recurrented method because we can’t know which sequence you’d want. If you want a recurrent perm space you need to use get_rapplied() with a recurrent sequence.)

(There’s no get_sliced method because slicing is done using Python’s normal slice notation, e.g. perm_space[4:-7].)

get_degreed(degrees)

Get a degreed version of this PermSpace restricted to certain degrees.

You may use a single integer for degrees to limit it to permutations of that degree, or a sequence of integers like (1, 3, 7).

get_partialled(n_elements):

Get a partialled version of this PermSpace, i.e. a k-permutation.

combinationed:

A combination version of this perm space. (i.e. a CombSpace.)

get_typed(perm_type)

Get a typed version of this PermSpace where perms are of a custom type.

Properties for removing a variation from a perm space: (A new perm space is returned, the original one does not get modified)

purified

A purified version of this PermSpace, i.e. with all variations removed.

unrapplied

A version of this PermSpace without a custom range.

undapplied

A version of this PermSpace without a custom domain.

unrecurrented

A version of this PermSpace with no recurrences.

unfixed

An unfixed version of this PermSpace.

unsliced

An unsliced version of this PermSpace.

undegreed

An undegreed version of this PermSpace.

unpartialled

A non-partial version of this PermSpace.

uncombinationed

A version of this PermSpace where permutations have order.

untyped

An untyped version of this PermSpace.

Perm

class Perm(perm_sequence, perm_space=None)

A permutation of items from a PermSpace.

In combinatorics, a permutation is a sequence of items taken from the original sequence.

Example:

>>> perm_space = PermSpace('abcd')
>>> perm = Perm('dcba', perm_space)
>>> perm
<Perm: ('d', 'c', 'b', 'a')>
>>> perm_space.index(perm)
23

apply(sequence, result_type=None)

Apply the perm to a sequence, choosing items from it.

This can also be used as sequence * perm. Example:

>>> perm = PermSpace(5)[10]
>>> perm
<Perm: (0, 2, 4, 1, 3)>
>>> perm.apply('growl')
'golrw'
>>> 'growl' * perm
'golrw'

Specify result_type to determine the type of the result returned. If result_type=None, will use tuple, except when other is a str or Perm, in which case that same type would be used.

as_dictoid

A dict-like interface to a Perm.

classmethod coerce(item, perm_space=None)

Coerce item into a perm, optionally of a specified PermSpace.

degree

The permutation’s degree, i.e. the number of transformations needed to produce it.

You can think of a permutation’s degree like this: Imagine that you’re starting with the identity permutation, and you want to make this permutation, by switching two items with each other over and over again until you get this permutation. The degree is the number of such switches you’ll have to make.

domain

The permutation’s domain.

For a non-dapplied permutation, this will be range(len(sequence)).

get_neighbors(*, degrees=(1, ), perm_space=None)

Get the neighbor permutations of this permutation.

This means, get the permutations that are close to this permutation. By default, this means permutations that are one transformation (switching a pair of items) away from this permutation. You can specify a custom sequence of integers to the degrees argument to get different degrees of relation. (e.g. specify degrees=(1, 2) to get both the closest neighbors and the second-closest neighbors.)

index(member)

Get the index number of member in the permutation.

Example:

>>> perm = PermSpace(5)[10]
>>> perm
<Perm: (0, 2, 4, 1, 3)>
>>> perm.index(3)
4

inverse

The inverse of this permutation, i.e. the permutation that we need to multiply this permutation by to get the identity permutation.

This is also accessible as ~perm.

Example:

>>> perm = PermSpace(5)[10]
>>> perm
<Perm: (0, 2, 4, 1, 3)>
>>> ~perm
<Perm: (0, 3, 1, 4, 2)>
>>> perm * ~perm
<Perm: (0, 1, 2, 3, 4)>

items

A viewer of a perm’s items, similar to dict.items().

This is useful for dapplied perms; it lets you view the perm (both index access and iteration) as a sequence where each item is a 2-tuple, where the first item is from the domain and the second item is its corresponding item from the sequence.

length

The permutation’s length.

n_cycles

The number of cycles in this permutation.

If item 1 points at item 7, and item 7 points at item 3, and item 3 points at item 1 again, then that’s one cycle. n_cycles is the total number of cycles in this permutation.

unrapplied

A version of this permutation without a custom sequence. (Using range(len(sequence)).)

undapplied

A version of this permutation without a custom domain.

uncombinationed

A non-combination version of this permutation.