Exploring Permutations under Constraints in Python
In my previous post, I introduced you to the basics of permutations and combinations in Python, focusing on simple scenarios with one or two lists and no constraints. Now, let’s take a deeper dive and explore Python code for generating permutations while considering specific constraints. Whether you’re working with data analysis, optimization, or combinatorial problems, understanding how to handle constraints within permutations is essential.
Brief Background
The ‘zip’ method
The zip method combines two lists element-wise, creating tuples from corresponding elements at the same index. Let’s look at a couple of examples:
def zip_2_lists(list_1, list_2):
# Assumption: list_1 and list_2 have the same length
zipped = zip(list_1, list_2)
list_zipped = list(zipped)
return list_zippedExample1:
list_1 = ["A", "B", "C"]
list_2 = ["X", "Y", "Z"]
list_zipped = zip_2_lists(list_1, list_2)
print(list_zipped)
# Output: [('A', 'X'), ('B', 'Y'), ('C', 'Z')]Example2:
list_1 = ["C", "B", "A"]
list_2 = ["X", "Z", "Y"]
list_zipped = zip_2_lists(list_1, list_2)
print(list_zipped)
# Output: [('C', 'X'), ('B', 'Z'), ('A', 'Y')]Sorting Two Lists by Length
Before we explore permutations, let’s create a utility function to sort two lists by length. We’ll use this later since the permutations method requires the length of the shorter list.
def sort_by_length(list_1, list_2):
# If the first list is shorter than the second, swap them
if len(list_1) < len(list_2):
list_1, list_2 = list_2, list_1
return list_1, list_2Generating Permutations of a Single List with a Given Length
Now, let’s generate permutations of a single list with a specified length (smaller than the list’s original length). We’ll use the itertools.permutations() function:
from itertools import permutations
def generate_permutations_of_length(list_1, length):
# Get all permutations of list_1 with the specified length
perm = permutations(list_1, length)
return perm
list_1 = [1, 2, 3]
length = 2
perms_single_list_by_length = generate_permutations_of_length(list_1, length)
print(list(perms_single_list_by_length))
# Output: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]My previous article provided detailed exploration of this subject.
Generating Unique Permutations under Constraints in Python
Iterating Through Permutations and Collecting Valid Pairs
- Sorting Lists: We’ve already sorted the input lists by length to ensure consistency. Now, let’s proceed to generate permutations.
- Generating Permutations: We’ll use the
itertools.permutationsfunction to generate all possible permutations of the longer list, takenlen(list_2)at a time. This ensures that each permutation matches the length of the shorter list. - Checking Conditions: For each permutation, we’ll zip it with
list_2to create pairs. Then, we’ll check each pair using thecheck_conditionsfunction. If a pair satisfies the specified conditions, we’ll add it to a local list of valid pairs. - Avoiding Duplicates: To ensure uniqueness, we’ll keep track of valid permutations. If a local list of valid pairs is not empty and is not already in our list of valid permutations, we’ll append it.
- Final Result: Our final result will be a list of valid permutations that meet the constraints.
Here’s the updated code snippet:
def unique_permutations(list_1, list_2):
# Sort lists by length
list_1, list_2 = sort_by_length(list_1, list_2)
# Initialize a list to store valid permutations
valid_perms = []
# Generate all permutations of the longer list taken len(list_2) at a time
for perm in generate_permutations_of_length(list_1, len(list_2)):
# Zip the permutation with list_2
list_zipped = zip_2_lists(perm, list_2)
# Initialize a local list of valid pairs
local_list_of_perms = []
# Check each pair
for (value1, value2) in list_zipped:
if check_conditions(value1, value2):
local_list_of_perms.append((value1, value2))
# Append if the local list is not empty and not already in valid_perms
if len(local_list_of_perms) != 0 and local_list_of_perms not in valid_perms:
valid_perms.append(local_list_of_perms)
# Return the list of valid permutations
return valid_permsExample Usage
Assuming you run the following code:
list_1 = [1, 2, 3, 4, 5]
list_2 = [1, 2, 3]
print("unique_permutations(list_1 =", list_1, ", list_2 =", list_2, "):")
print(unique_permutations(list_1, list_2))The output will be a list of valid permutations:
[[(1, 1), (2, 2), (3, 3)],
[(1, 1), (2, 2), (4, 3)],
[(1, 1), (2, 2), (5, 3)],
[(1, 1), (3, 2), (2, 3)],
[(1, 1), (3, 2), (4, 3)],
[(1, 1), (3, 2), (5, 3)],
[(1, 1), (4, 2), (2, 3)],
[(1, 1), (4, 2), (3, 3)],
[(1, 1), (4, 2), (5, 3)],
[(1, 1), (5, 2), (2, 3)],
...
[(5, 1), (4, 2), (1, 3)],
[(5, 1), (4, 2), (2, 3)],
[(5, 1), (4, 2), (3, 3)]]Implementing the ‘check_conditions’ Function
The check_conditions function plays a crucial role in determining whether a pair of values from the two lists can be paired together. In our case, we want to exclude pairs with identical values. Here’s the implementation:
def check_conditions(value1, value2):
"""
Checks if the conditions for a valid pairing are met.
In this example, we exclude pairs with identical values.
Modify this function according to your specific constraints.
"""
return value1 != value2Putting It All Together
Now let’s integrate the check_conditions() function into our unique_permutations() implementation. We’ll use the same example lists:
list_1 = [1, 2, 3, 4, 5]
list_2 = [1, 2, 3]
# Generate unique permutations based on the conditions
unique_perms = unique_permutations(list_1, list_2)
# Print the resulting pairs
for perm in unique_perms:
print(perm)The output will be:
[(4, 3)]
[(5, 3)]
[(3, 2), (2, 3)]
[(3, 2), (4, 3)]
[(3, 2), (5, 3)]
[(4, 2)]
[(4, 2), (5, 3)]
[(5, 2), (2, 3)]
...
[(5, 1), (4, 2), (1, 3)]
[(5, 1), (4, 2), (2, 3)]
[(5, 1), (4, 2)].Now, thanks to our check_conditions() function, we’ve ensured that duplicated numbers no longer appear in the output pairs.
Customizing Constraints
Feel free to customize the check_conditions() function to suit your specific constraints. You can exclude pairs based on other conditions, such as avoiding certain combinations or enforcing specific rules.
Permutations by Extracting Data from Excel Files
In this section, we will extract data from Excel files and perform unique permutations using Python and pandas. Let’s break down the process step by step.
Extracting Data from Excel Files
To start, let’s import the data from the Excel file into pandas DataFrames. The Excel file is named “full_info.xlsx” and includes two tabs named “Sheet1” and “Sheet2.” The content of these two sheets is as follows:
Sheet1:
Names | Number | Place | List
------------------------------------
name1 | 21 | Paris | a, b, d, c
name2 | 8 | NY | d, a
name3 | 16 | NY | b, d
name4 | 23 | London | b, a
name5 | 27 | Paris | a, d, bSheet2:
Names | Number | Place | Char
------------------------------
nameA | 10 | NY | b
nameB | 1 | NY | d
nameC | 2 | London | cThis code will import the data:
import pandas as pd
if __name__ == '__main__':
# Read the Excel file
xls = pd.ExcelFile('full_info.xlsx')
# Read 'Sheet1' and 'Sheet2' into DataFrames
df1 = xls.parse('Sheet1', names=['Names', 'Number', 'Place', 'List'])
df2 = xls.parse('Sheet2', names=['Names', 'Number', 'Place', 'Char'])Interested readers can find more information about the data structure DataFrame in pandas.
Unique Permutations
Now let’s find unique permutations of pairs of names from both DataFrames. We’ll define a function unique_permutations_df that takes df1 and df2 as input and returns a list of valid permutations. We’ll also define the conditions for a valid pairing:
- The ‘Number’ value in Sheet1 must be at least 5 greater than the corresponding ‘Number’ in Sheet2.
- The ‘Place’ values cannot be the same.
- The ‘Char’ value from Sheet2 should be in the ‘List’ from Sheet1.
def unique_permutations_df(df1, df2):
# Sort lists by length
df1, df2 = sort_by_length(df1, df2) # Implement sort_by_length function
# Initialize a list of valid permutations
valid_perms = []
# Generate all permutations of the longer list taken len(df2) at a time
df1_all_permutations = generate_permutations_of_length(df1.iterrows(), len(df2)) # Implement generate_permutations_of_length function
for perm in df1_all_permutations:
# Zip the permutations with the rows from df2
list_zipped = zip_2_lists(perm, df2.iterrows()) # Implement list_zipped function
# Initialize a local list of valid permutations
local_list_of_perms = []
for (index1, row1), (index2, row2) in list_zipped:
# Check the conditions for a valid pairing
if check_conditions_df(row1, row2): # Implement check_conditions_df function
# If the conditions are met, add the pair to the current permutation
local_list_of_perms.append((row1['Names'], row2['Names']))
if len(local_list_of_perms) != 0 and local_list_of_perms not in valid_perms:
# Append if local-list is not empty and not already in valid_perms
valid_perms.append(local_list_of_perms)
# Return the list of valid permutations
return valid_permsConditions Function
Let’s define the check_conditions_df() function, that verifies the conditions for a valid pairing:
def split_and_strip(str_in):
return [x.strip() for x in str_in.split(',')]
def check_conditions_df(row1, row2):
if (int(row1['Number']) >= int(row2['Number']) + 5 and
row1['Place'] != row2['Place'] and
row2['Char'] in split_and_strip(row1['List'])):
return True
return FalseBy applying these modifications, you’ll be able to find valid permutations of names from both DataFrames. The full code’s output will be:
[[('name1', 'nameA')],
[('name1', 'nameA'), ('name5', 'nameB')],
[('name1', 'nameB')],
[('name1', 'nameC')],
[('name5', 'nameB'), ('name1', 'nameC')],
[('name5', 'nameB')],
[('name4', 'nameA'), ('name1', 'nameB')],
[('name4', 'nameA'), ('name1', 'nameC')],
[('name4', 'nameA')],
[('name4', 'nameA'), ('name5', 'nameB'), ('name1', 'nameC')],
[('name4', 'nameA'), ('name5', 'nameB')],
[('name5', 'nameA'), ('name1', 'nameB')],
[('name5', 'nameA'), ('name1', 'nameC')],
[('name5', 'nameA')]]Appendix:
Understanding df.iterrows()
The iterrows() method in pandas returns an iterator that yields pairs of index and row data for each row in a DataFrame. Specifically, it provides a way to iterate over the rows of a DataFrame, where each iteration yields a tuple containing:
- The index of the current row.
- A pandas Series (or dictionary-like object) representing the data in that row.
For example, for the following code:
for index, row in df1.iterrows():
print("index:", index)
print("row:")
print(row)
print("---")The output is:
index: 0
row:
Names name1
Number 14
Place London
List b, c, a, d
Name: 0, dtype: object
---
index: 1
row:
Names name2
Number 30
Place NY
List b, c, d, a
Name: 1, dtype: object
---
index: 2
row:
Names name3
Number 12
Place London
List b, c
Name: 2, dtype: object
---
index: 3
row:
Names name4
Number 27
Place London
List d, b, a
Name: 3, dtype: object
---
index: 4
row:
Names name5
Number 12
Place London
List c, a, d, b
Name: 4, dtype: object
---Accessing Elements in the Row
To access specific elements within a row, you can use the column names as keys. For example:
for index, row in df1.iterrows():
print("Place:", row["Place"])The output:
Place: Paris
Place: NY
Place: NY
Place: London
Place: ParisIn this case, we’re accessing the “Place” column for each row.
Thank you for reading!
Farther Reading:
Reading the following article after this one is highly recommended:
