如何在时间方面优化这段代码？

Question

我已经写好了代码，但它运行起来需要很长时间。我需要进一步优化它。这里的 k 可以变化，它可以是 2、3 或 4，取决于用户。请在这里帮助我。

from itertools import combinations

def get_all_combinations(input_list, k):
    for item in combinations(input_list, k):
        yield list(set(list(item)))

input_list = [1, 2, 1, 2, 3]
k = 3
lst = []
for i in range(1, k + 1):
    for item in get_all_combinations(input_list, i):
        if len(item) > i - 1:
            lst.append(item)
print(len(lst))

>>17


#[[1], [2], [1], [2], [3], [1, 2], [1, 2], [1, 3], [1, 2], [2, 3], [1, 2], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

- Serum

Answer 1

尝试这个：

>>> input_list = [1, 2, 1, 2, 3]
>>> k = 3
>>> [list(set(el)) for i in range(1, k+1) for el in itertools.combinations(input_list, i) if len(set(el))>i-1]
[[1], [2], [1], [2], [3], [1, 2], [1, 2], [1, 3], [1, 2], [2, 3], [1, 2], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

- Grzegorz Skibinski

---

根据OP的逻辑 - 每个项目都需要是一个集合。 - RomanPerekhrest

非常抱歉浪费您的时间...但我在查询代码中进行了一些小修改...您能否请看一下并帮助我优化解决方案...谢谢@GrzegorzSkibinski - Serum

Answer 2

测试一下：

 from itertools import combinations

def get_all_combinations(input_list,k):
    l = []
    for item in combinations(input_list, k):
        l.append( list(set(list(item))))
    return l

input_list = [1, 2, 1, 2, 3]
k = 3
lst = []
for i in range(1,k+1):
    gac = []
    gac = get_all_combinations(input_list, i)
    for item in gac:
        if len(item) > i-1:
            lst.append(item)
print(len(lst))

基于链接的基础上

- Shahab Rahnama

---

非常抱歉浪费了您的时间...但我在查询代码中修改了一点东西...您可以看一下并帮我优化解决方案吗？谢谢@ShahabRahnama - Serum

@Remus 测试一下！ - Shahab Rahnama

Answer 3

使用以下版本，您的处理速度将快近两倍：

from itertools import combinations

def get_all_combinations(input_list, k):
    for i in range(1, k + 1):
        for item in combinations(input_list, i):
            s = set(item)
            if len(s) >= i:
                yield list(s)

input_list = [1, 2, 1, 2, 3]
k = 3
lst = list(get_all_combinations(input_list, k))
print(lst)

输出结果保持不变：

[[1], [2], [1], [2], [3], [1, 2], [1, 2], [1, 3], [1, 2], [2, 3], [1, 2], [1, 3], [2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

- RomanPerekhrest

---

很抱歉 @RomanPerekhrest，浪费了您的时间... 但我在查询代码中进行了一些小修改... 您能否请看一下并帮助我优化解决方案... 谢谢 - Serum

@Remus，我的方法仍然适用 - 为什么你不使用它？有什么问题吗？ - RomanPerekhrest

我的意思是现在我可以在print中使用len(lst)，但我认为获取列表中的序列会以某种方式使用时间，这可能与O(n)有关...我们能否使用更口语化的方式，比如使用count或类似的东西？... - Serum

@Remus，主要条件已经涵盖并有答案。对于新的条件，请创建新的问题。 - RomanPerekhrest

我会记住的...非常感谢你的帮助。 - Serum

Answer 4

如果这是作业，你的教师可能正在寻找这个。

lst = [list(c) for i in range(k) for c in combinations(input_list, i+1) if len(set(c)) > i]

- Robert Co