Skip to content

Instantly share code, notes, and snippets.

@tomy0000000

tomy0000000/Python Combinatorics Cheat Sheet.ipynb

Created July 7, 2021 17:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tomy0000000/8dacf21fb0d4ba84897621dc65f14a0f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tomy0000000/8dacf21fb0d4ba84897621dc65f14a0f to your computer and use it in GitHub Desktop.
Download ZIP
Python Combinatorics Cheat Sheet
Display the source blob
Display the rendered blob
Raw
Python Combinatorics Cheat Sheet.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import itertools\n",
"import math"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Overview\n",
"\n",
"| | Linear | Circular | Non-Ordinal |\n",
"| -------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
"| Non-Repetitive | ![Permutation](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fffa6967dcb9faf21389c000ac6fa97d4e74aa3) | ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa9e4f710bab4992f92a33220df36ffce879d351) | ![Combination](https://wikimedia.org/api/rest_v1/media/math/render/svg/37eeb6cd5b9062227eb3c5a5965e1d602d95acfb) |\n",
"| Repetitive | ![Product](https://wikimedia.org/api/rest_v1/media/math/render/svg/0090b61e9671b6ec5177265d5ddbacab91c687de) | ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/13f576f1658e4840247d6d55803652e8694c6c3c) | ![Counting multisets](https://wikimedia.org/api/rest_v1/media/math/render/svg/10f7530e7df6e04dac8268fae3c2221f05adfd9c) |"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Permutation\n",
"\n",
"![Permutation](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fffa6967dcb9faf21389c000ac6fa97d4e74aa3)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"12"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.factorial(4) // math.factorial(4 - 2)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"12"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(list(itertools.permutations(\"ABCD\", 2)))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('A', 'B'),\n",
" ('A', 'C'),\n",
" ('A', 'D'),\n",
" ('B', 'A'),\n",
" ('B', 'C'),\n",
" ('B', 'D'),\n",
" ('C', 'A'),\n",
" ('C', 'B'),\n",
" ('C', 'D'),\n",
" ('D', 'A'),\n",
" ('D', 'B'),\n",
" ('D', 'C')]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(itertools.permutations(\"ABCD\", 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Product\n",
"\n",
"![Product](https://wikimedia.org/api/rest_v1/media/math/render/svg/0090b61e9671b6ec5177265d5ddbacab91c687de)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"16"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"4 ** 2"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"16"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(list(itertools.product(\"ABCD\", repeat=2)))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('A', 'A'),\n",
" ('A', 'B'),\n",
" ('A', 'C'),\n",
" ('A', 'D'),\n",
" ('B', 'A'),\n",
" ('B', 'B'),\n",
" ('B', 'C'),\n",
" ('B', 'D'),\n",
" ('C', 'A'),\n",
" ('C', 'B'),\n",
" ('C', 'C'),\n",
" ('C', 'D'),\n",
" ('D', 'A'),\n",
" ('D', 'B'),\n",
" ('D', 'C'),\n",
" ('D', 'D')]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(itertools.product(\"ABCD\", repeat=2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Combination\n",
"\n",
"![Combination](https://wikimedia.org/api/rest_v1/media/math/render/svg/37eeb6cd5b9062227eb3c5a5965e1d602d95acfb)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.factorial(4) // (math.factorial(2) * math.factorial(4 - 2))"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(list(itertools.combinations(\"ABCD\", 2)))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(itertools.combinations(\"ABCD\", 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Counting multisets\n",
"\n",
"![Counting multisets](https://wikimedia.org/api/rest_v1/media/math/render/svg/10f7530e7df6e04dac8268fae3c2221f05adfd9c)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"math.factorial(4 + 2 - 1) // (math.factorial(2) * math.factorial(4 - 1))"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(list(itertools.combinations_with_replacement(\"ABCD\", 2)))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('A', 'A'),\n",
" ('A', 'B'),\n",
" ('A', 'C'),\n",
" ('A', 'D'),\n",
" ('B', 'B'),\n",
" ('B', 'C'),\n",
" ('B', 'D'),\n",
" ('C', 'C'),\n",
" ('C', 'D'),\n",
" ('D', 'D')]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(itertools.combinations_with_replacement(\"ABCD\", 2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Reference\n",
"\n",
"* [Python Documentation - itertools](https://docs.python.org/3/library/itertools.html)\n",
"* [Wikipedia (zh)](https://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6#%E6%80%BB%E7%BB%93)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment