Combinations in Python

Combinations involve selecting items from a set without considering order. Unlike permutations, which arrange objects in a specific order, combinations focus on possible arrangements where order is irrelevant. Python's "itertools" library offers predefined methods for both permutations and combinations, providing efficient tools for these calculations. Subsequent sections will delve into multiple approaches for finding combinations in Python.

Importing the Required Library

We are provided with a particular "pre-defined" function in the Python's itertools library, which is used for finding out the permutations and the combinations for a given set of items. The itertools is a built-in module in Python and hence, it does not require any prior installation. To get started with using the library, we need to import it first, as explained below:

Python’s Itertool module provides us with different methods to work on the iterators(sequences like list, tuple, str) and produce desired iterators as output through them.

Methods to Create Combinations in Python

There are majorly three ways to create combinations in Python. They are listed below:

• Combinations using iterators
• Combinations using iterators with replacements
• Combinations using recursion

We will cover combinations using iterators and with replacements in detail, and without using the iterators. Later we will also discuss the recursive approach of finding combinations.

Combinations Using Iterators

It is very easy to generate combinations using itertools. The syntax for the same is given below

Syntax:

Here, itertools is the module that we have imported. Then, we pass an iterable to the method. The iterable could be anything such as a list, set or tuple. And then, we pass r which will produce the r length subsequences of the elements, from the iterable we passed as the input.

Let us see examples to clearly understand its usage.

Code for combinations example:

If we now see the output, then we will get the location of the itertools object as given below:

Output:

So, the combinations() function basically returns an iterator. We can loop through the iterator to get our results. But, we can also convert it into a list and get all the combinations generated through the iterator in a list. Let us look at the example below to convert it into a list.

Code to convert iterator output to a list:

Output:

Let us also take an example of generating combinations using a string.

Code to produce combinations of strings:

Output:

We can also join the output we got using the join in Python. Let us see the code for the same.

Code to join the output tuples into strings:

Output:

Here, we have generated all the 3 length combinations from the string. Also, we have used join to join the results into strings which are actually in tuples.

Some important points about generating combinations through itertools are:

• The combinations are generated in form of "tuples", which are lexicographically ordered, according to the order of the input iterable provided. So, if the input is provided in an sorted order, the combination tuple will also be in a sorted order. For example, suppose if we provide a lexicographically sorted input such as abcd to our combinations function, then all the output we will get will be sorted in a lexicographical order. For more clarity, refer the code below :

Code:

Output:

In the above example, we passed the alphabets in a lexicographically sorted (dictionary) order. And, all the combinations we got as our output is in sorted order.

• The elements are treated uniquely on the basis of their positions and not their values. So, if we pass any unique input, there will not be any repetition of values in the combinations produced. So, if we pass repeated elements, then their combinations will be in the order of their positions. For example, let us look at a code below which has both repeated and non-repeated elements. You can see, how the combination differs for each of the outputs, based on their positions.

Code:

Output:

Combinations With Range()

Another great feature of the iteratools.combinations() is that it can take any iterable as its first argument, which means, we can even pass lazy sequences such as range to it.

Code to produce combinations using range:

Output:

In the above example, you could see that we passed a range of 4, and our iteratools.combinations() produced all the combinations from 0 to 3. Because, the range starts from 0 and is exclusive of the last value, so it started from 0, and ended before 4 (that is till3).

Combinations with replacement in itertools

Now that we have learned enough about using combinations with itertools, let us look into a new function provided by itertools -- combinations_with_replacement .

As the name suggests, the combinations_with_replacement returns all the $l$ length sequences of elements we have passed as input, allowing each of the elements to be repeated more than once.

The syntax for the same is given below:

Syntax:

It will produce $l$ length combinations of the iterable passed as input. Also, it will repeat each of the individual elements more than once. That means, for every element, it will also form a combination with itself, apart from the other elements in the list.

Let us look at an example to understand this better.

Code to demonstrate combinations with replacement:

Output:

In the above example, you can see that each of the characters has produced a combination with every other character, including itself. Like, 'a' have a combination with 'a', 'b', 'c', 'd', and similarly for all other characters of our input string.

Fact: The number of items returned by combinations with replacement is =

$\frac{(n+r-1)! }{r!(n-1)!}$

where, $n > 0$. What if we provide input with repeating characters? Let us see an example below when we provide an input with repeating characters.

Code:

Output:

You can clearly see in this example that we have duplicates involved in our output. Since this is a combination with replacement, every element has a combination with itself and with all other elements of the list.

Combinations Without Itertools

We might sometime also have the necessity to generate the combinations without using the itertools module provided by python. In that case, the Python documentation provides us with the code for generating the combinations without using the itertools. There are definitely other ways to implement the combinations without using the itertools. But, let us look at the code for generating combinations without itertools.

Code:

So, with the above code, we can generate the combinations without actually using any library or module. The code is provided by the official Python documentation.

Combinations With Replacement and Without Itertools

Again, we can find the combinations with replacement and also without using any itertools or python libraries. The code is provided by the official Python documentation. You can refer to the below code for generating the Combinations without replacement (and without itertools).

Code:

So, the above code will produce the combinations with replacement, similar to the ones we coded above for the combinations with replacement using itertools.

Combinations Using Recursion

Now, we will learn how to compute combinations using the recursion. Since we are asked to calculate all the possible combinations, hence we have to use the backtracking in this case. Before that, let us get a crisp overview of backtracking.

Just a recap : Backtracking is an algorithmic technique that considers searching in every possible combination for solving a computational problem. It uses recursion to find the solution by building a solution step by step increasing the values with time.

Intuition: As we already know, in every backtracking problem we are expected to be very clear about two things before approaching the problem. Let us know about each of them clearly.

• Base Case : The first thing we have to fix is the base case. Every problem of backtracking has some base case, which determines when our recursive process will end and we will stop the recursion. In this case, we know that whenever the size of our current list becomes equal to $K$ ($K$ is the length of combination we want to produce), then we have to stop the recursion and add the generated combination till that point to our final answer.
• Condition : We should note that at every step we will choose an element at index $i$, add it to our temporary $path$, and call the recursion. And, at the next step, we will pop off the element from our $path$. So, basically, we will be following the pick and un-pick method to generate all the combinations of the input.

Let us see the code for the above discussed approach.

Code:

Output:

Explanation: In the above code, we are basically taking a number $i$, and generating all the combinations corresponding to it, by recursively calling our backtracking function. Once our recursive function is called, we pop off the current element from our temporary path, again call the recursive function and proceed with the next. So, basically, we are picking up the element once and then un-picking the element the next time.

Read More

After having learned about the combinations in Python, I would highly recommend you to pick these scaler articles below to further enhance your learning :

• Permutations in Python
• Lexicographical Order in Python
• Recursion in Python