Possible combination of a nested list in python

user_7639382 0
Viewed 1994

If I have a list of lists and want to find all the possible combination from each different indices, how could I do that?

For example:

list_of_lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

I want to find

all_possibility = [[1, 5, 9], [1, 8, 6], [4, 2, 9], [4, 8, 3], [7, 2, 6], [7, 5, 3]]

where

  • [1,5,9]: 1 is 1st element of [1, 2, 3], 5 is 2nd element of [4, 5, 6], 9 is 3rd element of [7, 8, 9].

  • [1,8,6]: 1 is 1st element of [1, 2, 3], 8 is 2nd element of [7, 8, 9], 6 is 3rd element of [4, 5, 6].

and so on.

(Edited) Note: I would like the result to be in the same order as the original element of the list. [1, 8, 6] but not [1, 6, 8] because 8 is the 2nd element of [7, 8, 9].

python-3.x list python
3 Answers

What you're looking for is the Cartesian product, in Python itertools.product:

>>> import itertools
>>> list_of_lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> all_possibility = list(itertools.product(*list_of_lists))
>>> print(all_possibility)
[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 6, 7), (1, 6, 8),
 (1, 6, 9), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 6, 7),
 (2, 6, 8), (2, 6, 9), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 5, 7), (3, 5, 8), (3, 5, 9),
 (3, 6, 7), (3, 6, 8), (3, 6, 9)]

If you want permutations based on the indices rather than the values, you can use itertools.combinations to get the possible indices, then use those indices to get the respective values from the sub-lists, like this:

>>> list_of_lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> length = 3
>>> all_indices = list(itertools.permutations(range(length), length))
>>> all_possibility = [[l[i] for l,i in zip(list_of_lists, indices)] for indices in all_indices]
>>> print(all_possibility)
[[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 6, 7], [3, 4, 8], [3, 5, 7]]
user_62751030

I have to consider the indices as well. For example, (1, 4, 7) is excluded because 1, and 4 both are the 1st element from the list of the lists (from [1, 2, 3] and [4, 5, 6]). And actually (1, 4, 7) all of them are from the first component of the nested list. I need the cases with all the different indices.

So you actually just want to get the possible permutations of a “list selector” for each index in the output, i.e. these are what you are trying to get:

>>> list(itertools.permutations(range(3), 3))
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

And once you have that, you just need to translate into your list_of_lists where you access each index from the specified sublist:

>>> [[list_of_lists[k][i] for i, k in enumerate(comb)] for comb in itertools.permutations(range(3), 3)]
[[1, 5, 9], [1, 8, 6], [4, 2, 9], [4, 8, 3], [7, 2, 6], [7, 5, 3]]
user_2160740

In a spirit of @poke's approach, here is the cases for number of elements differ than the number of the list in the lists. (Previously, there are 3 elements in individual list where 3 sub-lists in the list).

list_of_lists = [[1, 2], [3, 4], [5, 6], [7, 8]]

We expect every (0, 1) pairs from the list of lists, or

all_possibility = [[1, 4], [1, 6], [1, 8], [3, 2], [3, 6], [3, 8], \
                   [5, 2], [5, 4], [5, 8], [7, 2], [7, 4], [7, 6]]

The code:

permutation_cases = list(itertools.permutations(range(2), 2))
select_from = list(itertools.combinations(range(len(list_of_lists)), 2))

all_possibility = []
for selecting_index in select_from:
        selected = [list_of_lists[i] for i in selecting_index ]
        cases = list([selected[k][i] for i, k in enumerate(comb)] for comb in permutation_cases)
        for item in cases:
            all_possibility.append(item)
print(all_possibility)
user_76393820
Related