..
   Copyright 2009-2015 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)
      <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 :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]
         <Perm: (2, 1, 0)>
      
   .. 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: ('d', 'c', 'b', 'a')>
      >>> 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: (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 :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: (0, 2, 4, 1, 3)>
         >>> 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: (0, 2, 4, 1, 3)>
         >>> ~perm
         <Perm: (0, 3, 1, 4, 2)>
         >>> perm * ~perm
         <Perm: (0, 1, 2, 3, 4)>
      
   .. 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

