#+BEGIN_COMMENT
.. title: Python Itertools Combinations
.. slug: python-itertools-combinations
.. date: 2020-11-09 16:11:26 UTC-08:00
.. tags: python,standard library,slip note
.. category: Python
.. link:
.. description: The python Combinations function.
.. type: text
.. status:
.. updated:
.. has_math: True
#+END_COMMENT
#+OPTIONS: ^:{}
#+TOC: headlines 2
#+PROPERTY: header-args :session ~/.local/share/jupyter/runtime/kernel-24c67be9-19db-4f42-9f79-7dcc16187faa-ssh.json
#+BEGIN_SRC python :results none :exports none
%load_ext autoreload
%autoreload 2
#+END_SRC
* What?
This is a brief note on the python [[https://docs.python.org/3/library/itertools.html#itertools.combinations][itertools.combinations]] function.
#+begin_src python :results none
from itertools import combinations
#+end_src
To make sure it's behaving the way I think it will I'll also use some other built-ins.
#+begin_src python :results none
from itertools import count
from math import factorial
from math import comb as n_choose_k
#+end_src
* Okay, but what?
The =combinations= function takes two arguments:
- iterable: the source that you want to make combinations from
- r: the length of the sequences you want to make
It returns all the r-length subsequences in the iterable ([[https://www.wikiwand.com/en/Combination][combinations]]).
** A Count Function
The number of combinations of length /k/ for a sequence of length /n/ is the [[https://www.wikiwand.com/en/Binomial_coefficient][Binomial Coefficient]].
\begin{align}
\binom{n}{k} &= \frac{n(n-1) \cdots (n - k + 1)}{k(k-1) \cdots 1}\\
&= \frac{n!}{k!(n-k)!}
\end{align}
I originally implemented a function for this but it turns out it got added to python as of 3.8 ([[https://docs.python.org/3/library/math.html#number-theoretic-and-representation-functions][number-theoretic functions]]). Here's my translation for reference. The calculation is actually really fast so you don't gain a lot from these toy problems using the standard library, but since it's there, why not?
#+begin_src python :results none
def n_choose_k_one(n: int, k: int) -> int:
"""The Binomial Coefficient
Args:
n: the length of the source set
k: the length of the combinations
Returns:
the number of combinations in the sequence
"""
return factorial(n) / (factorial(k) * factorial(n - k))
#+end_src
** Example One
This is given as an example in the documentation.
#+begin_src python :results output :exports both
EXPECTEDS = "AB AC AD BC BD CD".split()
SOURCE = "ABCD"
k = 2
for combination, expected, total in zip(combinations(iterable=SOURCE, r=k), EXPECTEDS, count(start=1)):
print(f" - {combination}")
assert "".join(combination) == expected
n = len(SOURCE)
assert total == n_choose_k(n, k)
#+end_src
#+RESULTS:
: - ('A', 'B')
: - ('A', 'C')
: - ('A', 'D')
: - ('B', 'C')
: - ('B', 'D')
: - ('C', 'D')
Note that it treated the string as a sequence and returns a tuple, not a sub-string. Also note that it doesn't swap orders, so "D" is never a first entry, for instance.
** Example Two
This one is also from the documentation.
#+begin_src python :results output :exports both
SOURCE = list(range(4))
n = len(SOURCE)
EXPECTEDS = [(0, 1, 2),
(0, 1, 3),
(0, 2, 3),
(1, 2, 3)]
k = 3
for combination, expected, total in zip(combinations(SOURCE, k), EXPECTEDS, count(start=1)):
print(combination)
assert combination == expected
assert total == n_choose_k(n, k)
#+end_src
#+RESULTS:
: (0, 1, 2)
: (0, 1, 3)
: (0, 2, 3)
: (1, 2, 3)