Набор Питона Power of a List

Question

Я пытаюсь реализовать функцию для генерации powerset списка xs,

Общая идея состоит в том, что мы проходим через элементы xs и выберите, включать ли x или нет. Проблема, с которой я сталкиваюсь, заключается в том, что withX заканчивается равным [None] (единый список с None) потому что я думаю) s.add(x) возвращается None,

Это не домашнее задание, это упражнение по взлому интервью.

def powerSetBF(xs):
    powerSet = [] 
    powerSet.append(set([]))
    for x in xs:
        powerSetCopy = powerSet[:]
        withX = [s.add(x) for s in powerSetCopy] # add x to the list of sets 
        powerSet = powerSet.extend(withX) # append those entries
    return powerSet

Answer 1

Посмотрите на powerset пример из itertools рецепты:

from itertools import chain, combinations

def powerset(iterable):
    "list(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))

Для range целых чисел до длины заданного списка, сделать все возможное combinations а также chain они вместе как один объект.

Answer 2

Вот рекурсивное решение, которое не использует никаких модулей:

def pset(myset):
  if not myset: # Empty list -> empty set
    return [set()]

  r = []
  for y in myset:
    sy = set((y,))
    for x in pset(myset - sy):
      if x not in r:
        r.extend([x, x|sy])
  return r

print(pset(set((1,2,3,4))))
#[set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, 
# {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}]

Answer 3

import itertools

def powerset(L):
  pset = set()
  for n in xrange(len(L) + 1):
    for sset in itertools.combinations(L, n):
      pset.add(sset)
  return pset

powerset([1, 2, 3, 4])

результат

set([(1, 2), (1, 3), (1, 2, 3, 4), (1,), (2,), (3,), (1, 4), (4,), (), (2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3), (3, 4), (2, 4)])

Исходный код для itertools.combinations можно найти здесь, который имеет несколько аккуратных оптимизаций:

https://docs.python.org/3/library/itertools.html