用于升序子列表组合的更快解决方案

Question

这是我上一个问题的后续问题：从子列表中检索所有可能的升序组合

对于较大的列表，解决此问题的代码确实很慢。这是我目前的解决方案：

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_list1 = [[0], [1, 4, 6], [2]]
get_ascending_combinations(example_list1)
>> [(0, 1), (0, 4), (0, 2), (1, 2), (0, 1, 2), (0, 6)]
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)]

如示例所示，它应该只按升序进行组合。另一个限制是，只允许与每个唯一子列表中的一个项目进行组合。

然而，这个代码在较大的列表上确实很慢，因为可能的组合数量要大得多。如何制作一个更快的算法来做到这一点？请参阅下面的示例列表。

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]]

Answer 1

好的，我把这段代码放在这里，尽管它可能需要进一步检查。

方法

我的方法是，首先构建所有的order-2组合，然后通过在每个order-(n-1(组合中添加每个后续子列表中的可接受数字(即1(来创建order-n组合(n=3，4，…，length_of_list(。该组合中没有数字，并且为2。在该组合中使用的最后一个子列表之后。

性能

我用您的example_list2检查了结果，它还可以，但我的实现速度慢了大约2倍，因为它有一些开销。然后我创建了一个mid_example列表，其中包含来自large_example的前14个子列表，结果非常惊人。在我的笔记本电脑上：

>>> timeit("get_ascending_combinations(mid_example)", number=50, globals=globals())
40.589324300000044
>>> a=AscendingCombos(mid_example)
>>> timeit("a.calculate()", number=50, globals=globals())
0.23768389999997908

注意事项

我没有检查输出，尽管我有理由相信它是正确的。

我无法在large_example上执行这两个过程，因为这两个程序都阻止了我正在执行的其他作业，尽管我希望再次确认的速度

代码

class AscendingCombos():
def __init__(self, mainlist):
self.mainlist = mainlist
self.maindict = {k:v for k,v in enumerate(mainlist)}
self.mainrange = set(range(len(self.mainlist)))
self.out = {}

def calculate(self):
##order 2
self.out[2] = []
for combo in combinations(self.maindict.keys(), 2):
for first in self.maindict[combo[0]]:
for second in self.maindict[combo[1]]:
if second > first:
self.out[2].append([list(combo),[first,second]])
##order 3+        
for order in range(3,len(self.mainlist)+1):
self.out[order] = []
for prevcombo in self.out[order-1]:
cands = self.mainrange.difference(
prevcombo[0]).difference(
range(prevcombo[0][-1]))
for cand in cands:
##i = self.index[prevcombo[0]].append(self.mainlist.index(self.mainlist[cand]))
for nextnum in self.maindict[cand]:
if nextnum > prevcombo[1][-1]:
self.out[order].append([prevcombo[0]+[cand],prevcombo[1]+[nextnum]])
return self.out
def tolist(self):
for order in range(2,len(self.mainlist)+1):
print(order, [c[1] for c in self.out[order]]) 

Answer 2

使用递归函数可以完成：

def get_ascending_combinations(a):
if len(a) == 0:
return []
for left in get_ascending_combinations(a[:-1]):
yield left
for right in a[-1]:
if left[-1] < right:
yield left + [right]
for right in a[-1]:
yield [right]

>>> for x in get_ascending_combinations([[0], [1, 4], [2]]):
...     print(x)
[0]
[0, 2]
[0, 1]
[0, 1, 2]
[0, 4]
[1]
[1, 2]
[4]
[2]

但由于组合的数量是指数级的，所以不可能将所有组合作为一个列表：

>>> it = get_ascending_combinations(large_example)
>>> for x in range(10):
...     print(next(it))
[19]
[19, 93]
[19, 50]
[19, 50, 93]
[19, 91]
[19, 91, 93]
[19, 89]
[19, 89, 93]
[19, 89, 91]
[19, 89, 91, 93]