4 Best Ways to Create a List of Permutations in Python : Chris
by: Chris
blow post content copied from Be on the Right Side of Change
click here to view original post
Problem Formulation: Imagine you want to generate all possible arrangements of a sequence of items, such that each item is in a unique position in each arrangement. This is known as finding the permutations of the sequence.
For example, given the sequence [1, 2, 3], the desired output is a list of permutations like [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)].
This article will explore methods to achieve this in Python.
Method 1: Using itertools.permutations
The itertools module in Python provides a function permutations() which takes a sequence and returns an iterator over the permutations of the sequence. This method is simple and effective for generating permutations.
Here’s an example:
import itertools items = [1, 2, 3] permutations_list = list(itertools.permutations(items)) print(permutations_list) # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
This code snippet imports the itertools module and uses its permutations function to create an iterator over all possible permutations of the list items. We then convert this iterator to a list to print out the permutations.
Method 2: Using Recursion
A recursive function can be designed to generate the permutations of a sequence. This involves swapping elements at each position with the rest and recursively calling the permutation function for the remaining part of the sequence.
Here’s an example:
def permute(sequence, start, end):
if start == end:
print(sequence)
else:
for i in range(start, end + 1):
sequence[start], sequence[i] = sequence[i], sequence[start] # swap
permute(sequence, start + 1, end)
sequence[start], sequence[i] = sequence[i], sequence[start] # swap back
items = [1, 2, 3]
permute(items, 0, len(items) - 1)
Output:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]In this code snippet, we define a function permute that takes the sequence and the starting and ending indices. It uses recursion to swap each element and generate permutations. It prints the permutations for each complete arrangement.
Method 3: Using Heap’s Algorithm
Heap’s Algorithm is a classic method for generating permutations that works by generating the permutations of n-1 elements of the sequence and then adding the nth element into every possible position.
Here’s an example:
def generate_permutations(n, sequence):
if n == 1:
print(sequence)
else:
for i in range(n-1):
generate_permutations(n-1, sequence)
if n % 2 == 0:
sequence[i], sequence[n-1] = sequence[n-1], sequence[i]
else:
sequence[0], sequence[n-1] = sequence[n-1], sequence[0]
generate_permutations(n-1, sequence)
items = [1, 2, 3]
generate_permutations(len(items), items)
The code snippet defines a recursive function generate_permutations that takes the size of the sequence and the sequence itself. It generates permutations by recursively swapping elements using Heap’s Algorithm and prints each permutation.
Method 4: Using the sympy library
The sympy library, typically known for symbolic mathematics, also includes a utilities module which can generate permutations. This is useful if you are already working within a sympy environment.
Here’s an example:
from sympy.utilities.iterables import multiset_permutations items = [1, 2, 3] permutations_list = list(multiset_permutations(items)) print(permutations_list)
In this code snippet, we import the multiset_permutations function from the sympy utilities module. We then use this function to generate an iterable of permutations of the list items and convert it into a list.
Summary/Discussion
- Using itertools.permutations:
- Strength: Incredibly simple and straightforward to use.
- Weakness: Can consume a lot of memory with larger input sequences.
- Using recursion:
- Strength: Doesn’t require any additional modules.
- Weakness: Can be less efficient and harder to understand for those not familiar with recursion.
- Using Heap’s Algorithm:
- Strength: More efficient than naive recursion.
- Weakness: Algorithm could be non-intuitive for some users.
- Using the sympy library:
- Strength: Integrates well if already using sympy for other computations.
- Weakness: Overhead of using a heavy library for a task achievable with standard libraries.
For quick and easy implementation, itertools.permutations is very handy. If learning or teaching recursion and backtracking algorithms, then methods 2 and 3 with recursion and Heap’s algorithm may be preferable.
When working in a scientific computing environment, sympy could be a natural choice.
Python One-Liners Book: Master the Single Line First!
Python programmers will improve their computer science skills with these useful one-liners.
Python One-Liners will teach you how to read and write “one-liners”: concise statements of useful functionality packed into a single line of code. You’ll learn how to systematically unpack and understand any line of Python code, and write eloquent, powerfully compressed Python like an expert.
The book’s five chapters cover (1) tips and tricks, (2) regular expressions, (3) machine learning, (4) core data science topics, and (5) useful algorithms.
Detailed explanations of one-liners introduce key computer science concepts and boost your coding and analytical skills. You’ll learn about advanced Python features such as list comprehension, slicing, lambda functions, regular expressions, map and reduce functions, and slice assignments.
You’ll also learn how to:
- Leverage data structures to solve real-world problems, like using Boolean indexing to find cities with above-average pollution
- Use NumPy basics such as array, shape, axis, type, broadcasting, advanced indexing, slicing, sorting, searching, aggregating, and statistics
- Calculate basic statistics of multidimensional data arrays and the K-Means algorithms for unsupervised learning
- Create more advanced regular expressions using grouping and named groups, negative lookaheads, escaped characters, whitespaces, character sets (and negative characters sets), and greedy/nongreedy operators
- Understand a wide range of computer science topics, including anagrams, palindromes, supersets, permutations, factorials, prime numbers, Fibonacci numbers, obfuscation, searching, and algorithmic sorting
By the end of the book, you’ll know how to write Python at its most refined, and create concise, beautiful pieces of “Python art” in merely a single line.
Get your Python One-Liners on Amazon!!
February 08, 2024 at 01:10AM
Click here for more details...
=============================
The original post is available in Be on the Right Side of Change by Chris
this post has been published as it is through automation. Automation script brings all the top bloggers post under a single umbrella.
The purpose of this blog, Follow the top Salesforce bloggers and collect all blogs in a single place through automation.
============================
Post a Comment