This is a follow-up question of my previous question: Retrieve all possible combinations of ascending integers from sublists
The code that works for this problem is really slow for bigger lists.
This is my solution so far:
from typing import List, Tuple
from itertools import product, combinations
def is_ascending(t: tuple) -> bool:
return sorted(t) == list(t)
def get_ascending_combinations(a: List[List[int]]) -> List[Tuple, ...]]:
all_combs = []
add_comb = all_combs.append
input_length = len(a) + 1
for comb_length in range(2, input_length):
for main_comb in combinations(a, comb_length):
for comb in product(*main_comb):
if is_ascending(comb):
add_comb(comb)
return all_combs
example_list = [[0], [1, 4], [2]]
get_ascending_combinations(example_list)
>> [(0, 1), (0, 4), (0, 2), (1, 2), (0, 1, 2)]
example_list2 = [[0], [1, 4], [2], [5, 6]]
get_ascending_combinations(example_list2)
>> [(0, 1), (0, 4), (0, 2), (0, 5), (0, 6), (1, 2), (1, 5), (1, 6), (4, 5), (4, 6), (2, 5),
(2, 6), (0, 1, 2), (0, 1, 5), (0, 1, 6), (0, 4, 5), (0, 4, 6), (0, 2, 5), (0, 2, 6),
(1, 2, 5), (1, 2, 6), (0, 1, 2, 5), (0, 1, 2, 6)]
As shown in the example it should only make combinations in ascending order. Another restriction is that is only allowed to make combinations with only one item from each unique sublist.
However this code is really slow on larger lists, since the number of possible combinations is much larger. How can make a faster algorithm that does this? See the example list below.
large_example = [[19, 67], [21, 43], [64], [47, 65, 69, 90], [48, 70], [0, 27, 63], [1], [2], [3],
[4, 53], [5], [6], [7, 57], [8, 58], [9], [10], [11, 82], [12, 37], [13],
[14, 77], [15], [16], [17], [18, 74], [20], [22], [23], [24, 30], [25], [26],
[28], [29], [31], [32], [33], [34], [35], [36], [38], [39], [40], [41], [78],
[79], [80], [46, 84], [85], [86], [87], [88], [89], [91], [50], [93]]
