.. Copyright 2009-2017 Ram Rachum. This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License, with attribution to "Ram Rachum at ram.rachum.com" including link. The license may be obtained at http://creativecommons.org/licenses/by-sa/3.0/ .. _perm_space_and_perm: :class:`PermSpace` and :class:`Perm` ==================================== :class:`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 :class:`PermSpace` is a :class:`Perm`, i.e. a permutation. This is similar to :func:`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 :class:`PermSpace`: >>> perm_space = PermSpace(3) >>> perm_space[2] >>> tuple(perm_space) (, , , , , ) The members are :class:`Perm` objects, which are sequence-like objects that have extra functionality. (See documentation of :class:`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. :class:`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 :class:`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`_ (:class:`Comb`\ s) instead of perms. :class:`Comb`\ s are like :class:`Perm`\ s 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 :class:`PermSpace`, meaning that the perms will use the class you provide rather than the default :class:`Perm`. This is useful when you want to provide extra functionality on top of :class:`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 :meth:`get_degreed()` on it with the desired degrees. If you want to make a degreed perm space non-degreed, access its :attr:`undegreed` property. The same is true for all other variations. A perm space that has none of these variations is called **pure**. .. method:: coerce_perm(perm) Coerce a sequence to be a permutation of this space. .. method:: 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] .. attribute:: length The :class:`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) .. method:: get_rapplied(sequence) Get a rapplied version of this :class:`PermSpace` that has a range of `sequence`. .. method:: get_dapplied(domain) Get a dapplied version of this :class:`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 :meth:`.get_rapplied` with a recurrent sequence.) .. method::get_fixed(fixed_map) Get a fixed version of this :class:`PermSpace`. `fixed_map` should be a `dict` of keys to sequence values. (There's no ``get_sliced`` method because slicing is done using Python's normal slice notation, e.g. ``perm_space[4:-7]``.) .. method:: 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)``. .. method:: get_partialled(n_elements): Get a partialled version of this :class:`PermSpace`, i.e. a `k-permutation`_. .. attribute:: combinationed: A combination version of this perm space. (i.e. a :class:`CombSpace`.) .. method:: get_typed(perm_type) Get a typed version of this :class:`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) .. attribute:: purified A purified version of this :class:`PermSpace`, i.e. with all variations removed. .. attribute:: unrapplied A version of this :class:`PermSpace` without a custom range. .. attribute:: undapplied A version of this :class:`PermSpace` without a custom domain. .. attribute:: unrecurrented A version of this :class:`PermSpace` with no recurrences. .. attribute:: unfixed An unfixed version of this :class:`PermSpace`. .. attribute:: unsliced An unsliced version of this :class:`PermSpace`. .. attribute:: undegreed An undegreed version of this :class:`PermSpace`. .. attribute:: unpartialled A non-partial version of this :class:`PermSpace`. .. attribute:: uncombinationed A version of this :class:`PermSpace` where permutations have order. .. attribute:: untyped An untyped version of this :class:`PermSpace`. :class:`Perm` ------------- .. class:: Perm(perm_sequence, perm_space=None) A permutation of items from a :class:`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_space.index(perm) 23 .. method:: 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.apply('growl') 'golrw' >>> 'growl' * perm 'golrw' Specify ``result_type`` to determine the type of the result returned. If ``result_type=None``, will use :class:`tuple`, except when ``other`` is a :class:`str` or :class:`Perm`, in which case that same type would be used. .. attribute:: as_dictoid A dict-like interface to a :class:`Perm`. .. classmethod:: coerce(item, perm_space=None) Coerce item into a perm, optionally of a specified :class:`PermSpace`. .. attribute:: 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. .. attribute:: domain The permutation's domain. For a non-dapplied permutation, this will be ``range(len(sequence))``. .. method:: 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.) .. method:: index(member) Get the index number of ``member`` in the permutation. Example: >>> perm = PermSpace(5)[10] >>> perm >>> perm.index(3) 4 .. attribute:: 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 >>> perm * ~perm .. attribute:: 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. .. attribute:: length The permutation's length. .. attribute:: 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. .. attribute:: unrapplied A version of this permutation without a custom sequence. (Using ``range(len(sequence))``.) .. attribute:: undapplied A version of this permutation without a custom domain. .. attribute:: uncombinationed A non-combination version of this permutation. .. _permutation: https://en.wikipedia.org/wiki/Permutation .. _permutations: https://en.wikipedia.org/wiki/Permutation .. _k-permutation: https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n .. _k-permutations: https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n .. _combinations: https://en.wikipedia.org/wiki/Combination