Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 30 minutes | Coding time: 10 minutes

Generating all combinations taking one element from each list in Python can be done easily using itertools.product function. It is a part of itertools module and is very useful in this case.

The short solution is as follows:

```
list = [list1, list2]
combinations = [p for p in itertools.product(*list)]
```

Read on to understand how this is working better.

The itertools module has been developed and is being maintained by Raymond D. Hettinger. In this article, we will focus on using product function of itertools to solve our problem mainly.

Our problem is to: "Generating all combinations taking one element from each list". In Mathematics, this is known as the cartesian product of the lists.

A cartesian product of two lists A and B is defined as follows:

```
cartesian product of A and B = (x, y) where x belongs to A and y belongs to B
```

In Python, itertools.product produces the cartesian product and the great advantage is that it can take any number of lists as input.

# Using itertools.product

To use itertools.product, we need to import itertools module in our Python code which is done as follows:

```
import itertools
```

As itertools.product will take lists as input, we need to create some lists. In Python, there are multiple ways to create lists and it is flexible to create long lists that follow a pattern or with random elements.

Some common ways to create lists in Python are as follows:

```
# to generate list as [2, 3, 4, 5]
list = list(range(2, 5))
# another approach
list = [2, 3, 4, 5]
# list with powers of two less than 1000
list = [2**j for j in range(1, 9)]
# list with same number (1) repeated 1000 times
list = [1] * 1000
```

There are multiple approaches to create lists and you should explore it as per your need. For our current example, we will create two lists namely list1 and list2.

```
list1 = list(range(5, 10))
list2 = [1, 2, 3]
```

Note that list1 and list2 has different number of elements.

Following this, we will create a final list where the elements will be the lists from which we will take elements.

```
list = [list1, list2]
```

Following this, you need to pass this final list "list" to itertools.product which will generate all combinations or cartesian product:

```
combination = [p for p in itertools.product(*list)]
```

At this point, we can print combinations and take a look at the combinations that has been generated.

```
print(combination)
```

Output:

```
[(5, 1), (5, 2), (5, 3), (6, 1), (6, 2),
(6, 3), (7, 1), (7, 2), (7, 3), (8, 1),
(8, 2), (8, 3), (9, 1), (9, 2), (9, 3)]
```

The complete code is as follows:

```
import itertools
list1 = list(range(5, 10))
list2 = [1, 2, 3]
list = [list1, list2]
combination = [p for p in itertools.product(*list)]
print(combination)
```

# Get number of combinations

To get the number of combinations, we can simply use the len function on the combination list which is the output.

```
length = len(combination)
print (length)
```

For our above example, it will give 15 combinations. Complete code:

```
import itertools
list1 = list(range(5, 10))
list2 = [1, 2, 3]
list = [list1, list2]
combination = [p for p in itertools.product(*list)]
print(len(combination))
```

Output:

```
15
```

In fact, this is same as the product of the lengths of the individual lists such as:

```
length = len(list1) * len(list2)
```

# Traversing the combinations

Let us work on traversing the combinations that we have generated as to do anything useful with the generated combinations, we need to traverse it and get the individual combinations.

The items can be traverse as follows:

```
for item in combination:
print(item)
# do some thing with item
```

It can be accessed by index as well:

```
item = combination[2] # 3rd (2+1) combination
element = item[1] # 2 element in item
```

Complete Python code:

```
import itertools
list1 = list(range(5, 10))
list2 = [1, 2, 3]
list = [list1, list2]
combination = [p for p in itertools.product(*list)]
for item in combination:
print(item)
# do some thing with item
# get number of element in item
length = len(item)
# print all individual items in item
for element in item:
print("Element in ", item, " : ", element)
```

Output:

```
(5, 1)
Element in (5, 1) : 5
Element in (5, 1) : 1
(5, 2)
Element in (5, 2) : 5
Element in (5, 2) : 2
...
```

With this, you have a good idea of traversing the different combinations.

# Example with 4 lists

```
import itertools
list1 = list(range(5, 10))
list2 = [1, 2, 3]
list3 = [100]
list4 = [-1, -2]
list = [list1, list2, list3, list4]
combination = [p for p in itertools.product(*list)]
print(combination)
```

Output:

```
[(5, 1, 100, -1), (5, 1, 100, -2), (5, 2, 100, -1), (5, 2, 100, -2),
(5, 3, 100, -1), (5, 3, 100, -2), (6, 1, 100, -1), (6, 1, 100, -2),
(6, 2, 100, -1), (6, 2, 100, -2), (6, 3, 100, -1), (6, 3, 100, -2),
(7, 1, 100, -1), (7, 1, 100, -2), (7, 2, 100, -1), (7, 2, 100, -2),
(7, 3, 100, -1), (7, 3, 100, -2), (8, 1, 100, -1), (8, 1, 100, -2),
(8, 2, 100, -1), (8, 2, 100, -2), (8, 3, 100, -1), (8, 3, 100, -2),
(9, 1, 100, -1), (9, 1, 100, -2), (9, 2, 100, -1), (9, 2, 100, -2),
(9, 3, 100, -1), (9, 3, 100, -2)]
```

What if one of the list is empty? In this case, it will return an empty list as cartesian product cannot take any element from the empty list so it will terminate with an empty list.

Code for empty list:

```
import itertools
list1 = list(range(5, 10))
list2 = []
list3 = [100]
list4 = [-1, -2]
list = [list1, list2, list3, list4]
combination = [p for p in itertools.product(*list)]
print(combination)
```

Output:

```
[]
```

You may wonder what will be the case if we pass only one list into the product function. In this case, it will simply return all elements of the list one by one.

```
import itertools
list1 = list(range(5, 10))
list = [list1]
combination = [p for p in itertools.product(*list)]
print(combination)
```

Output:

```
[(5,), (6,), (7,), (8,), (9,)]
```

With this, you have the complete knowledge of generating all combinations by taking one element from each list in Python. This is an useful process. Enjoy.