На этом шаге мы рассмотрим важное математическое понятии булеана: множества всех подмножеств. Булеаны используются в статистике, теории множеств, функциональном программировании, теории вероятностей и алгоритмическом анализе.

    Булеан (powerset) - это множество всех подмножеств заданного множества s, включающее пустое множество {}, исходное множество s и все прочие возможные подмножества исходного множества. Ниже даны несколько примеров.

    Пример 1:

множество: s = {1};

его булеан: P = {{},{1}}.

    Пример 2:

множество: s = {1, 2};

его булеан: P = {{},{1},{2},{1,2}}.

    Пример 3:

множество: s = {1, 2, 3};

его булеан: P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.

    Для вычисления булеана P_n множества s, состоящего из n элементов, можно использовать булеан P_n-1 подмножества s, состоящего из (n - 1) элемента. Пусть нам требуется вычислить булеан множества s = {1, 2, 3}.

1. Зададим начальное значение булеана Р₀ с нулем элементов как Р₀ = {{}}. Другими словами, это булеан пустого множества. Он содержит только само пустое множество.
   
   
2. Для создания на основе булеана P_n-1 множества, состоящего из (n - 1) элемента булеана P_n, состоящего из n элементов, возьмем один (произвольный) элемент х из множества s и включим все получающиеся подмножества в больший булеан P_n с помощью следующей процедуры.
   
   
3. Проходим по всем множествам p в P_n-1 и создаем новые подмножества, состоящие из объединения х и р. В результате получаем новое временное множество множеств T. Например, если Р₂ = {{}, {1}, {2}, {1, 2}}, то мы создадим временное множество множеств T = {{3}, {1, 3}, {2, 3}, {1, 2, 3}} путем добавления элемента х ко всем множествам из P₂.
   
   
4. Объединяем это новое множество множеств T с булеаном P_n-1 и получаем булеан P_n. Например, булеан Р₃ получается путем объединения временного множества T с булеаном Р₂ следующим образом: P₃ = T ∪ P₂.
   
   
5. Переходим на шаг 2 до тех пор, пока исходное множество s не окажется пустым.
   
   

    Далее вас ждут более подробные пояснения этой стратегии.

Функция reduce()

    Но сначала необходимо как следует разобраться с важной функцией Python, которую мы применим в нашем однострочнике: reduce(). Отметим, что сначала ее нужно импортировать из библиотекия functools. Функция принимает три аргумента:

  reduce(функция, итерируемый_объект, начальное_значение)   . 

    Аргумент функция определяет способ свертки двух значений x и у в одно (например, lambda x, y: x + y). Таким образом можно в цикле свертывать два значения итерируемый_объект (второй аргумент) в одно до тех пор, пока в итерируемый_объект не останется только одно значение. Аргумент начальное_значение - необязательный, если его не указать, Python будет использовать по умолчанию первое значение итерируемый_объект.

    Например, при вызове

  reduce(lambda x, y: x + y, [0, 1, 2, 3]) 

    В этом последнем примере, как вы могли заметить, значение x всегда было равно результату предыдущего вызова лямбда-функции. Аргумент x играет роль значения-накопителя, а аргумент y - обновляемого значения из итерируемый_объект. Такое поведение нацелено на "свертку" в цикле всех значений из итерируемый_объект в одно значение. Необязательный третий аргумент задает начальное значение для x. Все это позволяет описать агрегатор для последовательностей, как показано в следующем 93 шаге.

Арифметические операции над списками

    Прежде чем заняться непосредственно однострочником, вам нужно понимать, как работают еще две операции над списками. Первая из них - оператор конкатенации списков +, склеивающий два списка. Например, результат операции [1, 2] + [3, 4] - новый список [1, 2, 3, 4]. Вторая - оператор объединения |, производящий простую операцию объединения двух множеств. Например, результат выражения {1, 2} | {3, 4} - новое множество {1, 2, 3, 4}.

    На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг