I have a list problem that I am struggling to come up with a solution for. Say we have the following list:
[0, 1, [2, 3], 4]
I want to pass this through a function and return two “flattened” versions of the list:
[0, 1, 2, 4] and [0, 1, 3, 4]
As a further example, the list [0, 1, [2, 3], [4, 5, 6]] should return 6 lists in total (total should be the multiplication of the length of each sub-list). You could think of the main list as a journey and the sub-lists as different routes along the way, each permutation tracking the different paths you could take through the main list.
How can I retrieve a list of each of these permutations? I suspect recursion might be involved but I cannot conceptualize it. If it helps each element in the list is unique (in this example int, but for my purposes each element will be a unique tuple i.e. (0, 0), (1,0) etc)
Below is what I have so far:
def func(lst, i=0):
return_list = []
for x in lst:
if isinstance(x, tuple):
return_list.append(x)
else:
return_list.append(x[i-1])
return return_list
test_list = [(0, 0), (1, 0), [(1, 1), (2, 1)], (3, 0)]
for i in test_list:
if isinstance(i, list):
for j in range(len(i)):
new_path = func(test_list, j)
if new_path not in path_list:
path_list.append(new_path)
#path_list = [[(0, 0), (1, 0), (2, 1), (3, 0)], [(0, 0), (1, 0), (1, 1), (3, 0)]]
This code works for the simple case of [0, 1, [2, 3], 4] but only returns 3 results for an expanded case, i.e. [0, 1, [2, 3], [4, 5, 6]], per below:
...
test_list = [(0, 0), (1, 0), [(1, 1), (2, 1)], [(3, 0), (3, 1), (3, 2)]]
...
#path_list = [[(0, 0), (1, 0), (2, 1), (3, 2)], [(0, 0), (1, 0), (1, 1), (3, 0)], [(0, 0), (1, 0), (2, 1), (3, 1)]]
10
With thanks to @JNevill for the link to the answer, what I was looking for was the cartesian product of the lists. Solution below (eveything changed to singleton lists per @chepner):
def cartesian_product(ar_list):
if not ar_list:
yield ()
else:
for a in ar_list[0]:
for prod in cartesian_product(ar_list[1:]):
yield (a,)+prod
l = [[(0, 0)], [(1, 0)], [(1, 1), (2, 1)], [(2, 3), (3, 0), (1, 3)]]
print(list(cartesian_product(l)))
# [((0, 0), (1, 0), (1, 1), (2, 3)),((0, 0), (1, 0), (1, 1), (3, 0)), ((0, 0), (1, 0), (1, 1), (1, 3)), ((0, 0), (1, 0), (2, 1), (2, 3)), ((0, 0), (1, 0), (2, 1), (3, 0)), ((0, 0), (1, 0), (2, 1), (1, 3))]
1