..
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/
.. _intro:
Getting started with Combi
==========================
Combi is a Pythonic package for `combinatorics`_.
Combi lets you explore spaces of `permutations`_ and `combinations`_ as if they
were Python sequences, but without generating all the permutations/combinations
in advance. It lets you specify a lot of special conditions on these spaces. It
also provides a few more classes that might be useful in combinatorics
programming.
Let’s look at the simplest example of using Combi. Check out this $5 padlock
in the picture:
.. image:: /images/padlock.jpg
:align: right
I use this padlock for my gym locker, so people won’t steal my stuff when
I’m swimming in the pool. It has 8 buttons, and to open it you have to press
down a secret combination of 4 buttons. I wonder though, how easy is it to
crack?
>>> from combi import *
>>> padlock_space = CombSpace(range(1, 9), 4)
>>> padlock_space
``padlock_space`` is the space of all possible combinations for our padlock. At
this point, the combinations weren’t really generated; if we’ll ask for a
combination from the space, it’ll be generated on-demand:
>>> padlock_space[7]
As you can see, ``padlock_space`` behaves like a sequence. We can get a
combination by index number. We can also do other sequence-y things, like
getting the index number of a combination, or slicing it, or getting the length
using :func:`len`. This is a huge benefit because then we can explore these
spaces in a declarative rather than imperative style of programming. (i.e. we
don’t have to think about generating the permutations, we simply assume that
the permutation space exists and we’re taking items from it at leisure.)
Let’s try looking at the length of ``padlock_space``:
>>> len(padlock_space)
70
Only 70 combinations. That’s pretty lame... At 3 seconds to try a
combination, this means this padlock is crackable in under 4 minutes. Not very
secure.
In the example above, I used :class:`CombSpace`, which is a space of
combinations. It’s a thin subclass over :class:`PermSpace`, which is a space
of permutations. A combination is like a permutation, except order doesn’t
matter.
Now, because the permutations/combinations are generated on-demand, I can do
something like this:
>>> huge_perm_space = PermSpace(1000)
>>> huge_perm_space
This is a perm space of all permutations of the numbers between 0 and 999. It
is ginormous. The number of permutations is around 10**2500 (a number that far
exceeds the number of particles in the universe.) I’m not even going to show
its length in the shell session because the length number alone would fill the
entire page. And yet you can fetch any permutation from this space by index
number in a fraction of a second:
>>> huge_perm_space[7]
Note that the permutation ``huge_perm_space[7]`` is a sequence by itself, where every item is a number in ``range(1000)``.
Combi lets you specify a myriad of options on the the spaces that you create.
For example, you can make some elements be fixed:
>>> fixed_perm_space = PermSpace(4, fixed_map={3: 3,})
>>> fixed_perm_space
>>> tuple(fixed_perm_space)
(,
,
,
,
,
)
This limits the space and makes it smaller. This is useful when you’re making
explorations on a huge :class:`PermSpace` and want to inspect only a smaller
subset of it that would be easier to handle.
There are many more variations that you could have on a :class:`PermSpace` or a
:class:`CombSpace`. You can specify a custom domain and a custom range to a
space. You can constrain it to permutations of a certain degree (e.g.
``degrees=1`` to limit to transformations only.) You can do `k-permutations`_
by specifying the length of the desired permutations as ``n_elements``. You can
have the permutation objects be of a custom subclass that you define, so you
could provide extra methods on them that fit your use case. You can provide
sequences that have some items appear multiple times and Combi would be smart
about it and consider multiple occurrences of the same item to be
interchangable. You can also toggle that behavior so it would treat them as
unique. It’s very customizable :) For more information on doing that, please
refer to the documentation for :class:`PermSpace` and :class:`CombSpace`.
:class:`PermSpace` and :class:`CombSpace` are the flagship classes of Combi;
but it also provides a few more useful features. See :ref:`features
` and :ref:`documentation contents ` for more
info.
.. _combinatorics: https://en.wikipedia.org/wiki/Combinatorics
.. _permutations: https://en.wikipedia.org/wiki/Permutation
.. _combinations: https://en.wikipedia.org/wiki/Combination
.. _k-permutations: https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n