Understanding Products, Permutations, Combinations, Combinations With Replacement in Python
This article was written while following the 100 days of Code by PyBites. I would recommend anyone wanting to learn Python to subscribe and try this challenge:
If it’s been a while since you studied Mathematics and now you’re looking at itertools, you might get confused when understanding the difference between Products, Permutations, Combinations, and combinations_with_replacement functions.
This obviously applies to all other programming languages out there, as this article deals more with the mathematical concepts behind them more than the actual language implementation.
In order to illustrate the difference between the 4 functions, we’ll imagine an ‘input’, a bag of coloured balls. Let’s imagine Red, Green, Blue and Yellow coloured balls.
All of the above 4 functions will take as input a list of [“Red”, “Green”, “Blue”, “Yellow”] and a number.
Products
Let’s start with products. An example of a product call in Python would be:
product(["Red", "Green", "Blue", "Yellow"], repeat=3)Using our bag of coloured balls analogy, the result can be thought of as follows:
- The bag is filled with the 4 differently coloured balls.
- A ball is chosen at random, then put back in the bag. This is repeated for 3 times (according to the repeat parameter)
- The result of all 3 chosen balls is recorded in a list in the order they were chosen
Logically, a sample result we might get is [“Red”, “Red”, “Blue”].
If we repeat the above experiment infinitely, and discard any identical result (considering order as well), the final result will be identical to the iterable returned by the product function above.
In other words, the result from the product function includes all result possibilities from the experiment above.
This can be shown with the full result set, below. Think of any possible result from the above experiment and you will find the combination here:
('Red', 'Red', 'Red')
('Red', 'Red', 'Green')
('Red', 'Red', 'Blue')
('Red', 'Red', 'Yellow')
('Red', 'Green', 'Red')
('Red', 'Green', 'Green')
('Red', 'Green', 'Blue')
('Red', 'Green', 'Yellow')
('Red', 'Blue', 'Red')
('Red', 'Blue', 'Green')
('Red', 'Blue', 'Blue')
('Red', 'Blue', 'Yellow')
('Red', 'Yellow', 'Red')
('Red', 'Yellow', 'Green')
('Red', 'Yellow', 'Blue')
('Red', 'Yellow', 'Yellow')
('Green', 'Red', 'Red')
('Green', 'Red', 'Green')
('Green', 'Red', 'Blue')
('Green', 'Red', 'Yellow')
('Green', 'Green', 'Red')
('Green', 'Green', 'Green')
('Green', 'Green', 'Blue')
('Green', 'Green', 'Yellow')
('Green', 'Blue', 'Red')
('Green', 'Blue', 'Green')
('Green', 'Blue', 'Blue')
('Green', 'Blue', 'Yellow')
('Green', 'Yellow', 'Red')
('Green', 'Yellow', 'Green')
('Green', 'Yellow', 'Blue')
('Green', 'Yellow', 'Yellow')
('Blue', 'Red', 'Red')
('Blue', 'Red', 'Green')
('Blue', 'Red', 'Blue')
('Blue', 'Red', 'Yellow')
('Blue', 'Green', 'Red')
('Blue', 'Green', 'Green')
('Blue', 'Green', 'Blue')
('Blue', 'Green', 'Yellow')
('Blue', 'Blue', 'Red')
('Blue', 'Blue', 'Green')
('Blue', 'Blue', 'Blue')
('Blue', 'Blue', 'Yellow')
('Blue', 'Yellow', 'Red')
('Blue', 'Yellow', 'Green')
('Blue', 'Yellow', 'Blue')
('Blue', 'Yellow', 'Yellow')
('Yellow', 'Red', 'Red')
('Yellow', 'Red', 'Green')
('Yellow', 'Red', 'Blue')
('Yellow', 'Red', 'Yellow')
('Yellow', 'Green', 'Red')
('Yellow', 'Green', 'Green')
('Yellow', 'Green', 'Blue')
('Yellow', 'Green', 'Yellow')
('Yellow', 'Blue', 'Red')
('Yellow', 'Blue', 'Green')
('Yellow', 'Blue', 'Blue')
('Yellow', 'Blue', 'Yellow')
('Yellow', 'Yellow', 'Red')
('Yellow', 'Yellow', 'Green')
('Yellow', 'Yellow', 'Blue')
('Yellow', 'Yellow', 'Yellow')Permutations
permutations(["Red", "Green", "Blue", "Yellow"], 3)In a way, permutations are similar to Products, but with one big difference.
The experiment is changed as follows:
- The bag is filled with the 4 differently coloured balls.
- A ball is chosen at random, and left out of the bag. This is repeated for 3 times (according to the second parameter)
- The result of all 3 chosen balls is recorded in a list in the order they were chosen
Clearly, the possibilities here are less. For example [‘Blue’, ‘Blue’, ‘Green’] is not possible now, since Blue was left out of the bag once it was selected once.
In fact, the result of the above function is:
('Red', 'Green', 'Blue')
('Red', 'Green', 'Yellow')
('Red', 'Blue', 'Green')
('Red', 'Blue', 'Yellow')
('Red', 'Yellow', 'Green')
('Red', 'Yellow', 'Blue')
('Green', 'Red', 'Blue')
('Green', 'Red', 'Yellow')
('Green', 'Blue', 'Red')
('Green', 'Blue', 'Yellow')
('Green', 'Yellow', 'Red')
('Green', 'Yellow', 'Blue')
('Blue', 'Red', 'Green')
('Blue', 'Red', 'Yellow')
('Blue', 'Green', 'Red')
('Blue', 'Green', 'Yellow')
('Blue', 'Yellow', 'Red')
('Blue', 'Yellow', 'Green')
('Yellow', 'Red', 'Green')
('Yellow', 'Red', 'Blue')
('Yellow', 'Green', 'Red')
('Yellow', 'Green', 'Blue')
('Yellow', 'Blue', 'Red')
('Yellow', 'Blue', 'Green')Again, think of any possibility for the above experiment, and you will find that result above.
Combinations
combinations(["Red", "Green", "Blue", "Yellow"], 3For combinations, we will need to make a small change to the above experiment. Instead of recording the result in a list, we record it in a set. The difference here is that in sets the order doesn’t matter. Thus (“Red”, “Yellow”, “Green”) is considered the same result as (“Green”, “Yellow”, “Red”) and will only be recorded once.
Let’s repeat the above experiment with this changed rule:
- The bag is filled with the 4 differently coloured balls.
- A ball is chosen at random, and left out of the bag. This is repeated for 3 times (according to the second parameter)
- The result of all 3 chosen balls is recorded in a set
The possibilities for the above experiment are quite smaller. In fact only the following results are possible:
('Red', 'Green', 'Blue')
('Red', 'Green', 'Yellow')
('Red', 'Blue', 'Yellow')
('Green', 'Blue', 'Yellow')Again, remember that for combinations, we are treating the results as unordered. If you think of a result for the above experiment and you think of (‘Green’, ‘Blue’, ‘Red’), this is represented in the results here as (‘Red’, ‘Green’, ‘Blue’) which are equal.
Some of you might have noticed a similarity between the results of the Combination and the results of the Permutation. In fact, if we were to disregard the order in the Permutation results and remove duplicates, the result would be identical to the Combinations one.
This can be demonstrated by the following code (which sorts the results of the permutation, and removes duplicates):
product_result = list(permutations(["Red", "Green", "Blue", "Yellow"], 3))sorted_product_result = sorted(set([str(sorted(res)) for res in product_result]))print(*sorted_product_result, sep = '\n')
which would print
['Blue', 'Green', 'Red']
['Blue', 'Green', 'Yellow']
['Blue', 'Red', 'Yellow']
['Green', 'Red', 'Yellow']which is identical to the result above (Printed order being irrelevent).
combinations_with_replacement
Finally, there is Combinations_with_repetition. Simply put, this is the same as combinations, but with repetitions allowed. In our experiment, this means we put the coloured ball back in the bag upon being chosen:
combinations_with_replacement(["Red", "Green", "Blue", "Yellow"], 3)- The bag is filled with the 4 differently coloured balls.
- A ball is chosen at random, and then put back in the bag. This is repeated for 3 times (according to the second parameter)
- The result of all 3 chosen balls is recorded in a set
The result of the above function would be
('Red', 'Red', 'Red')
('Red', 'Red', 'Green')
('Red', 'Red', 'Blue')
('Red', 'Red', 'Yellow')
('Red', 'Green', 'Green')
('Red', 'Green', 'Blue')
('Red', 'Green', 'Yellow')
('Red', 'Blue', 'Blue')
('Red', 'Blue', 'Yellow')
('Red', 'Yellow', 'Yellow')
('Green', 'Green', 'Green')
('Green', 'Green', 'Blue')
('Green', 'Green', 'Yellow')
('Green', 'Blue', 'Blue')
('Green', 'Blue', 'Yellow')
('Green', 'Yellow', 'Yellow')
('Blue', 'Blue', 'Blue')
('Blue', 'Blue', 'Yellow')
('Blue', 'Yellow', 'Yellow')
('Yellow', 'Yellow', 'Yellow')Again, remember that order is irrelevant here. If you follow the above experiment and think of a possible result, you will find the result here.
Again, some of you might have noticed that the result of combination_with_replacement is the same as the product one, if we treat order as irrelevant and remove duplicate results.
In Python, the following would return the same result as combination_with_replacement:
product_result = list(product(["Red", "Green", "Blue", "Yellow"], repeat=3))sorted_product_result = sorted(set([str(sorted(res)) for res in product_result]))print(*sorted_product_result, sep = '\n')
