135 lines
4.9 KiB
Plaintext
135 lines
4.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "eaf3192f",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Lexicographic Permutations](https://projecteuler.net/problem=24)\n",
|
|
"\n",
|
|
"Some might say Python makes things a little *too* easy. Not only is there a `permutations` function in [itertools](https://docs.python.org/3/library/itertools.html) (part of the standard library), but it outputs the permutations in lexicographic order. We can even use [generator expressions](https://docs.python.org/3/tutorial/classes.html#generator-expressions) for memory efficiency."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "1296ba0e",
|
|
"metadata": {
|
|
"scrolled": true
|
|
},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"(2, 7, 8, 3, 9, 1, 5, 4, 6, 0)\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"from itertools import permutations\n",
|
|
"\n",
|
|
"perms = permutations((0,1,2,3,4,5,6,7,8,9))\n",
|
|
"\n",
|
|
"print(next(p for (i, p) in enumerate(perms) if i == 999999))"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "2c53cca7",
|
|
"metadata": {},
|
|
"source": [
|
|
"If you're desperate to implement your own function, you can use an algorithm from [here](https://en.wikipedia.org/wiki/Permutation). It turns out there are a lot of algorithms for generating permutations.\n",
|
|
"\n",
|
|
"One principle we can apply to write our own function is the idea that if we have all the possible permutations of the last $n-1$ items in a list, we can iterate through each of those permutations, and for each one, generate $n$ permutations of all $n$ of our items by inserting the first of our $n$ items in each possible spot of the sub-permutation (before index 0, before index 1, and so on, including *after* the very last index). As an example, the permutations of $(1, 2)$ are $\\{(1, 2), (2, 1)\\}$. If we insert $0$ in every possible spot of the first permutation, we get $\\{(0, 1, 2), (1, 0, 2), (1, 2, 0)\\}$; with the second permutation, we get $\\{(0, 2, 1), (2, 0, 1), (2, 1, 0)\\}$. Together, these are all the permutations of $(0, 1, 2)$.\n",
|
|
"\n",
|
|
"This lends itself to a pretty intuitive recursive algorithm."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "dfda83aa",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def perms(iterable):\n",
|
|
" t = tuple(iterable)\n",
|
|
" if len(t) == 0:\n",
|
|
" yield t\n",
|
|
" return\n",
|
|
" \n",
|
|
" x, *xs = t\n",
|
|
" for p in perms(xs):\n",
|
|
" for i in range(0, len(p)+1):\n",
|
|
" yield (*p[:i], x, *p[i:])"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "636adfe4",
|
|
"metadata": {},
|
|
"source": [
|
|
"Unfortunately, this implementation does not output the permutations in lexicographic order, so if you want to use it to solve the problem, you'll need to generate all $10!$ permutations and sort them, which will take longer and use more memory.\n",
|
|
"\n",
|
|
"This alternative implementation is less intuitive than the previous one, in my opinion, but does output the permutations in lexicographic order. It's based on an algorithm sometimes called the Fischer-Krause algorithm, but they were not the first to discover it. This implementation still has less features and worse performance than the itertools function, so you should probably just use the latter for practical purposes."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "39be309c",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def lexperms(iterable):\n",
|
|
" lst = list(iterable)\n",
|
|
" while True:\n",
|
|
" yield tuple(lst)\n",
|
|
" for i in reversed(range(0, len(lst)-1)):\n",
|
|
" if lst[i] < lst[i+1]:\n",
|
|
" break\n",
|
|
" else:\n",
|
|
" break\n",
|
|
" \n",
|
|
" for j in reversed(range(i+1, len(lst))):\n",
|
|
" if lst[i] < lst[j]:\n",
|
|
" lst[i], lst[j] = lst[j], lst[i]\n",
|
|
" lst[i+1:] = lst[i+1:][::-1]\n",
|
|
" break"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "cde4b894",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"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.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|