The study of permutations and combinations is concerned with determining the number of different ways of arranging and selecting objects out of a given number of objects, without actually listing them. There are some basic counting techniques which will be useful in determining the number of different ways of arranging or selecting objects. The two basic counting principles are given below:
Suppose an event E can occur in m different ways and associated with each way of occurring of E, another event F can occur in n different ways, then the total number of occurrence of the two events in the given order is m × n .
For example, if you roll a six-sided dice and a two sided coin, then there are 6 × 2 = 12 possible outcomes.
Therefore, this principle can be use in everyday life when you need to calculate the number of possibilities that exist when combining choices.
# The total number of possible combinations (dice, coin) can be calculated using the fundamental principle of counting.
# Number of choices for dice and coin
dice_choices = 6 # 1, 2, 3, 4, 5, 6
coin_choices = 2 # H, T
# Total combinations using the Multiplication Principle of Counting
total_combinations = dice_choices * coin_choices
print(f"Total number of possible combinations: {total_combinations}")Total number of possible combinations: 12If an event E can occur in m ways and another event F can occur in n ways, and suppose that both can not occur together, then E or F can occur in m + n ways.
# The total number of possible combinations (dice, coin) can be calculated using addition principle of counting.
# Number of choices for dice and coin
dice_choices = 6 # 1, 2, 3, 4, 5, 6
coin_choices = 2 # H, T
# Total combinations using the Addition Principle of Counting
total_combinations = dice_choices + coin_choices
print(f"Total number of possible combinations: {total_combinations}")Total number of possible combinations: 8A permutation is an arrangement of objects in a definite order.
The number of permutations of n objects taken all at a time, denoted by the symbol \(^nP_n\) , is given by
where \({n!}\) = n(n – 1) (n – 2) … 3.2.1, read as factorial n, or n factorial.
There are basically two types of permutation:
In this case, you can finds all possible arrangements of a set of objects. And here, the order of the objects is important.
The number of permutations of n things taken all at a time, when repetion of objects is allowed is \(n^n\).
The number of permutations of n objects, taken r at a time, when repetition of objects is allowed, is \(n^r\).
In this case, you cannot select the same item multiple times while arranging a set of items. Essentially, each item can only be used once in the arrangement, meaning the number of available choices decreases with each selection made.
The number of permutations of n objects taken r at a time, where 0 < r ≤ n, denoted by \(^nP_r\) , is given by
\[ ^nP_r = \frac{n!}{(n-r)!} \]
where:
- \(n\) is the number of elements in the set.
- \(r\) is the number of elements taken together.
In this case, when objects are identical, many arrangements will appear the same, so you need to divide by the number of ways to arrange the identical objects among themselves.
The number of permutations of n objects of which r1 are of one kind, r2 are of second kind, …, rk are of kth kind and the rest if any, are of different kinds is
\[ \frac{n!}{(r1!*r2!*r3!..rk)!} \]
This method is used to calculate the total number of outcomes when order doesn’t matter. Essentially, we are not interested in arranging rather in selecting r objects from given n objects.
There are also two types of combinations:
In this case, you can only select each item once when choosing a group from a set. For instance, picking lottery numbers, where each number drawn cannot be repeated.
The formula for calculating the number of combinations from \(n\) elements taken \(r\) at a time is given by:
\[^n C_r = \frac{n!}{(n-r)! r!}\]
In this case, when selecting items from a set, you can choose the same item multiple times. For instance, selecting flavors for ice cream cones, where you could choose two scoops of chocolate.
If we choose a set of r items from n types of items, where repetition is allowed and the number items we are choosing from is essentially unlimited, the number of selections possible is given by:
\[^n C_r = \frac{(r+n-1)!}{(n-1)! r!}\]
Let’s explore some examples to better understand these concepts.
These methods can be found in itertools package.
We can use itertools module to generate permutations of objects efficiently. Here’s how to use itertools for the three types of permutations that we’ve discussed lately:
1. Permutations of 𝑛 Different Objects (No Repetition)
For a set of 𝑛 distinct objects, itertools.permutations() can generate all possible permutations of those objects. This is for the case where you want to arrange all n different objects without repetition.
import itertools
# List of distinct objects
objects = ['A', 'B', 'C']
# Generate all permutations of the objects
permutations = list(itertools.permutations(objects))
# Output the permutations and the total number of permutations
print("Permutations of distinct objects:", permutations)
print("Total number of permutations:", len(permutations))Permutations of distinct objects: [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
Total number of permutations: 62. Permutations When Repetition of Objects is Allowed
In this case, itertools.product() can be used to simulate the scenario where repetition is allowed. The result will generate all possible combinations where the same object can appear multiple times.
# Generate all permutations of length 2, allowing repetition
permutations_with_repetition = list(itertools.product(objects, repeat=2))
# Output the permutations and the total number of permutations
print("Permutations with repetition allowed:", permutations_with_repetition)
print("Total number of permutations:", len(permutations_with_repetition))Permutations with repetition allowed: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
Total number of permutations: 9If you want to generate permutations for selecting and arranging a specific number of elements from a set.
Permutaion taking 2 elements together from a set of 3 elements:
\[ ^3P_2 = \frac{3!}{(3-2)!} = \frac{3!}{1!} = \frac{6}{1} = 6 \]
Permutation taking 3 elements together from a set of 3 elements:
\[ ^3P_3 = \frac{3!}{(3-3)!} = \frac{3!}{0!} = \frac{6}{0} = 6 \]
char_set = ['A', 'B', 'C'] # define a charater set of 3 elements
permutations1 = list(itertools.permutations(char_set, 2)) # permutations taking two elements
permutations2 = list(itertools.permutations(char_set, 3)) # permutations taking three elements
# Output the permutations taking two elements and taking three elements
print("Permutations of 2 elements from 3 elements:", permutations1)
print("Permutations of 3 elements from 3 elements:", permutations2)Permutations of 2 elements from 3 elements: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
Permutations of 3 elements from 3 elements: [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]3. Permutations When the Objects are Not Distinct
For permutations with non-distinct objects, itertools.permutations will still generate all permutations, but you need to account for repeated objects manually by removing duplicates after generating the permutations.
import itertools
# List of objects, some of which are repeated
objects = ['A', 'A', 'B']
# Generate all permutations and remove duplicates by converting to a set
distinct_permutations = set(itertools.permutations(objects))
# Output the distinct permutations and the total number of distinct permutations
print("Distinct permutations of non-distinct objects:", distinct_permutations)
print("Total number of distinct permutations:", len(distinct_permutations))Distinct permutations of non-distinct objects: {('B', 'A', 'A'), ('A', 'B', 'A'), ('A', 'A', 'B')}
Total number of distinct permutations: 3Now, let’s take a look at combinations
Combinations without Repetition
Combination taking 2 elements together from a set of 3 elements:
\[ ^3C_2 = \frac{3!}{(3-2)!2!} = \frac{3!}{1!*2!} = \frac{6}{2} = 3 \]
Combination taking 3 elements together from a set of 3 elements:
\[ ^3C_3 = \frac{3!}{(3-3)!3!} = \frac{3!}{0!*3!} = \frac{6}{6} = 1 \]
# import combinations using itertools package
from itertools import combinations
combination1 = list(combinations(char_set, 2)) # combination taking two elements
# Output the combination taking two elements and the total number of combinations
print("Combinations of 2 elements from 3 elements:", combination1)
print("Total number of combinations of 2 elements from 3 elements:", len(combination1))Combinations of 2 elements from 3 elements: [('A', 'B'), ('A', 'C'), ('B', 'C')]
Total number of combinations of 2 elements from 3 elements: 3combination2 = list(combinations(char_set, 3)) # combination taking three elements
# Output the combination taking three elements and the total number of combinations
print("Combinations of 2 elements from 3 elements:", combination2)
print("Total number of combinations of 3 elements from 3 elements:", len(combination2))Combinations of 2 elements from 3 elements: [('A', 'B', 'C')]
Total number of combinations of 3 elements from 3 elements: 1Combinations with Repetiton
This function generates all possible combinations of \(r\) elements from a given iterable, allowing elements to be selected multiple times. It’s useful when repetitions are allowed in the selection process.
Combination taking 2 elements together from a set of 3 elements:
\[ ^3C_2 = \frac{(2+3-1)!}{(3-1)!*2!} = \frac{4!}{2!*2!} = \frac{24}{2*2} = 6 \]
Combination taking 3 elements together from a set of 3 elements:
\[ ^3C_3 = \frac{(3+3-1)!}{(3-1)!*3!} = \frac{5!}{2!*3!} = \frac{120}{2*6} = 10 \]
from itertools import combinations_with_replacement
combination_with_replacement1 = list(combinations_with_replacement(char_set, 2)) #combination taking two elements with replacement
# Output the combination taking three elements and the total number of combinations
print("Combinations of 2 elements from 3 elements:", combination_with_replacement1)
print("Total number of combinations of 2 elements from 3 elements:", len(combination_with_replacement1))Combinations of 2 elements from 3 elements: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
Total number of combinations of 3 elements from 3 elements: 6combination_with_replacement2 = list(combinations_with_replacement(char_set, 3)) #combination taking three elements with replacement
# Output the combination taking three elements and the total number of combinations
print("Combinations of 3 elements from 3 elements:", combination_with_replacement2)
print("Total number of combinations of 3 elements from 3 elements:", len(combination_with_replacement2))Combinations of 3 elements from 3 elements: [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'C'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'C'), ('C', 'C', 'C')]
Total number of combinations of 3 elements from 3 elements: 10This article explores combinatorics, specifically permutations and combinations, implementing it using python. It provides mathematical theory and python implementation in solving broader problems.
Permutations and Combinations have been crucial in fields ranging from cryptography to the optimization of AI algorithms.
For instance, in machine learning is feature selection in model training.
Permutations: It can be used to generate different sets of features to test their performance, optimizing the model’s accuracy.
Combinations: It can be used to determine the number of ways features can be selected from a larger set, helping in reducing model complexity and improving interpretability.
I’d love any feedback you may have. Feel free to reach out and follow SOTA Insights for more such articles!