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:

2
2
2 2
3
5 0 9

Sample output:

4 4
0 81

The above code does the following:

1. It takes the input as N, where N is the number of elements in the list.
2. Then it takes the input as the elements of the list.
3. Then it creates a function called powerset which takes a list as an argument and returns all the subsets of that list.
4. 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.
5. The reduce function will return a list of lists.
6. The ivlst variable is used to store the values of the minimum and maximum of the subsets.
7. Then it iterates over the range from 1 to the length of the list.
8. For each iteration, it appends the multiplication of minimum and maximum of the subset to the ivlst list.
9. 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.

CodePudding user response：

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

CodePudding user response：

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