Powerset рекурсивный, список понимания Python3

Question

Я новичок в Python3 и пытаюсь сделать рекурсивную функцию powerset. Следует использовать понимание списка.

Я написал:

def powerset(seq):
    if not seq:
       return [[]]
    return powerset(seq[1:]) + [[seq[0]] + n for n in powerset(seq[1:])]

Эта функция работает, но я получил отзыв, и мне сказали, что нет необходимости вызывать функцию два раза. Это сделало много вычислений. Он должен легко рассчитывать до 20 блоков питания. Так как мне быть? Я не могу заставить его работать без вызова функции дважды. Благодарю.

Answer 1

Просто посчитай powerset(seq[1:]) сохраните его в переменной и используйте дважды:

def powerset(seq):
    if not seq:
        return [[]]
    ps = powerset(seq[1:])
    return ps + [[seq[0]] + n for n in ps]

Разница в том, что таким образом вы используете ps дважды, но вы вычисляете это только один раз.

---

В качестве альтернативы, вы можете использовать двойное понимание списка (если вам нравится такая вещь...)

def powerset(seq):
    return [x for ps in powerset(seq[1:]) for x in ([seq[0]] + ps, ps)] if seq else [[]]

Здесь та же временная переменная ps определяется внутри понимания списка. Однако обратите внимание, что таким образом результаты будут в несколько ином порядке.

---

Я чувствую себя очень неясно. Я на самом деле не понимаю, как просто присвоение переменной может изменить это? Это значит то же самое?

Кажется, вы слишком много думаете о чистой математике. В программировании y = f(x) не означает "y совпадает с / синонимичным для f(x)", но "присваивает результат f (x) y".