Using min and max on sublists and creating a list without using "for loop" outside reduce function

Question

from functools import reduce
for _ in range(int(input())):
    N = int(input())
    l1 = list(map(int,input().split()))
    def powerset(lst):
        return reduce(lambda result, x: result + [subset + [x] for subset in result],
                      lst, [[]])
        
    #https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset

    lst = (powerset(l1))
    print(lst)
    ivlst = []
    
    for i in range(1, len(lst)):
        ivlst.append((min(lst[i])*max(lst[i])))
    print(min(ivlst), end=" ")
    print(max(ivlst))

Sample input:

Sample output:

4 4
0 81

The above code does the following:

It takes the input as N, where N is the number of elements in the list.
Then it takes the input as the elements of the list.
Then it creates a function called powerset which takes a list as an argument and returns all the subsets of that list.
Then it calls the reduce function on the powerset function with the list as the first argument and the empty list as the second argument.
The reduce function will return a list of lists.
The ivlst variable is used to store the values of the minimum and maximum of the subsets.
Then it iterates over the range from 1 to the length of the list.
For each iteration, it appends the multiplication of minimum and maximum of the subset to the ivlst list.
Finally, it prints the minimum and maximum of the ivlst list.

The time complexity is O(2^n) where n is the number of elements in the given set.

I need a way to not use the for loop for getting the min and max values of all sublists, rather I need to get a list containing multiplication of min and max values of all sublists as output from the powerset function itself.

It was a basic question to get a list of multiplication of maximum and minimum elements of all sublists but I am not satisfied with the time complexity of my solution. ty:) — Shivam, Sep 10 '22 at 05:42
Step 8: For each iteration, it appends the *(multiplication of) minimum and maximum of the subset to the ivlst list. — Shivam, Sep 10 '22 at 06:12
this should be in [codereview](https://codereview.stackexchange.com) — XxJames07-, Sep 10 '22 at 07:23
@XxJames07- How can I switch this question over to Code Review forum? — Shivam, Sep 10 '22 at 07:28
You can post it over there, go to https://codereview.stackexchange.com/questions/ask and paste the markdown in the body. — XxJames07-, Sep 10 '22 at 07:37

Mechanic Pig · Answer 1 · 2022-09-10T07:57:27.900

The equivalent code of your powerset function is as follows:

from itertools import islice

def powerset(lst):
    ret = [[]]
    for elem in lst:
        for subset in islice(ret, len(ret)):
            ret.append(subset + [elem])
    return ret

We no longer build and record the remaining subsets in the inner loop, but only record the minimum and maximum values of the subsets, so that our operating costs will be greatly reduced (from O(n * 2^n) to O(2^n), because the generation algorithm of power sets will not be faster than O(2^n), and the minimum and maximum values calculated for each subset are O(n)):

from itertools import islice

def powerset_extremum(lst):
    ret = [(float('inf'), float('-inf'))]
    for elem in lst:
        for min_, max_ in islice(ret, len(ret)):
            ret.append((min(min_, elem), max(max_, elem)))
    return ret

Simple test:

>>> powerset([2, 1, 4, 3])
[[],
 [2],
 [1],
 [2, 1],
 [4],
 [2, 4],
 [1, 4],
 [2, 1, 4],
 [3],
 [2, 3],
 [1, 3],
 [2, 1, 3],
 [4, 3],
 [2, 4, 3],
 [1, 4, 3],
 [2, 1, 4, 3]]
>>> powerset_extremum([2, 1, 4, 3])
[(inf, -inf),
 (2, 2),
 (1, 1),
 (1, 2),
 (4, 4),
 (2, 4),
 (1, 4),
 (1, 4),
 (3, 3),
 (2, 3),
 (1, 3),
 (1, 3),
 (3, 4),
 (2, 4),
 (1, 4),
 (1, 4)]

Then you can easily get their multiplication:

>>> from itertools import starmap, islice
>>> from operator import mul
>>> list(starmap(mul, islice(powerset_extremum([2, 1, 4, 3]), 1, None)))
[4, 1, 2, 16, 8, 4, 4, 9, 6, 3, 3, 12, 8, 4, 4]

I know that this does not meet your requirement of not using the for loop, but it is obviously much faster than eliminating the explicit for loop through some built-in functions after getting the power set.

score 0 · Answer 2 · answered Sep 10 '22 at 07:46

You could maximize the production of the powerset function, in fact, the Python itertools page has exactly a powerset recipe:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

or you can achieve by:

from more_itertools import powerset

Using min and max on sublists and creating a list without using "for loop" outside reduce function

2 Answers2