How to make this code more optimized in terms of time?

Question

I have a written the code here but it is taking much time. I need to optimize it more. The k here varies, it can be 2 or 3 or 4, depends on the user. Please help me out here.

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

Shahab Rahnama · Answer 1 · 2019-09-15T17:00:42.787

0

Test this:

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

base on link

edited Sep 15 '19 at 17:00

answered Sep 15 '19 at 14:36

Shahab Rahnama

982
1
7
14

I am sorry to waste your time... But I edited a small thing in the query code... Can you please look into it and help me with optimized solution... Thank you @ShahabRahnama – Serum Sep 15 '19 at 16:23
@Remus test it! – Shahab Rahnama Sep 15 '19 at 17:01

RomanPerekhrest · Answer 2 · 2019-09-15T14:43:16.643

0

With the following version your processing will go nearly twice as fast:

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)

The output remains the same:

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

edited Sep 15 '19 at 14:43

answered Sep 15 '19 at 14:36

RomanPerekhrest

88,541
4
65
105

I am sorry @RomanPerekhrest, to waste your time... But I edited a small thing in the query code... Can you please look into it and help me with optimized solution... Thank You – Serum Sep 15 '19 at 16:21
@Remus, my approach is still relevant - why don't you use it? what's is the issue? – RomanPerekhrest Sep 15 '19 at 16:25
I mean I now I can just do len(lst) in print but I think getting sequences in the list is using time somehow which might be relevant to O(n)... Can we use more verbal way, like using count or something like that?... – Serum Sep 15 '19 at 16:43
@Remus, the primary condition is covered and has answers. For new conditions - create new questions – RomanPerekhrest Sep 15 '19 at 16:47
I will that in mind... Thank you so much for the help – Serum Sep 15 '19 at 16:53

Grzegorz Skibinski · Answer 3 · 2019-09-15T14:41:04.273

0

Try this one:

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

edited Sep 15 '19 at 14:41

answered Sep 15 '19 at 14:37

Grzegorz Skibinski

12,624
2
11
34

1

according to the OP's logic - each item needs to be a **set** – RomanPerekhrest Sep 15 '19 at 14:38
I am sorry to waste your time... But I edited a small thing in the query code... Can you please look into it and help me with optimized solution... Thank you @GrzegorzSkibinski – Serum Sep 15 '19 at 16:22

score 0 · Answer 4 · answered Sep 15 '19 at 17:17

0

If this is meant to be homework, your instructor is probably looking for this.

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

answered Sep 15 '19 at 17:17

Robert Co

1,715
8
14

How to make this code more optimized in terms of time?

4 Answers4