PermSpace
and Perm
¶PermSpace
¶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.
fixed_map
, like
PermSpace('meow', fixed_map={0: 'm', 1: 'w'})
perm_space[56:100]
.degrees
argument either a single degree
(like 5
) or a tuple of different degrees (like (1, 3, 7)
)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
.is_combination=True
or use the subclass
CombSpace, then you’ll have a space of combinations (Comb
s)
instead of perms. Comb
s are like Perm
s except there’s
no order to the elements. (They are always forced into canonical order.)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:
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)
(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
.)
Properties for removing a variation from a perm space: (A new perm space is returned, the original one does not get modified)
Perm
¶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.
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.