Как найти множество чисел в информатике

Понятие “Множество” в математике и
информатике играет очень важную роль. В
математике существует целая теория множеств.

Первое знакомство с данной темой может быть у
учащихся как в начальной школе, если у них есть
курс информатики, так и у учащихся 5-6 классов,
которые раньше не изучали информатику. Данный
материал подготовлен для учащихся 5-6 классов.
Теме “Множества” желательно посвятить как
минимум 2 урока. Материал может быть полезен и для
преподавания информатики в начальной школе.

В курсе А.В. Горячева “Информатика в играх и
задачах”, рассчитанного на учащихся начальной
школы, тема “Множества” рассматривается и во 2
классе, и в 3 и в 4 классах. Естественно, что эта
тема прорабатывается с детьми не один урок, а
задания постепенно усложняются.

1. На первом уроке по теме “Множества” важно
сразу же дать четкие определения тех терминов,
которые потом будут использоваться в самых
различных заданиях. Урок основан на
использовании презентации (см.
Приложение 1).

Множество произошло от слова “много”. Но в
математике понятие “множество” используется
более широко.

Множество может объединять любое
количество предметов, чисел, существ. Каждый
предмет множества называется элементом
множества.

Множество, которое не содержит элементов,
называется пустым.

Множество может иметь подмножества.

Множества могут пересекаться, не
пересекаться, объединяться.

Равными называются множества, состоящие из одинакового
числа одинаковых элементов.

(Желательно, чтобы эти определения были
записаны учащимися в тетрадь, чтобы потом они
могли к ним вернуться.)

Эти определения необходимо закрепить на
простейших примерах, например: множество
животных имеет несколько подмножеств: рыбы,
птицы, звери, насекомые – и они не пересекаются.
Если же мы возьмем множество морских животных,
то оно будет пересекаться с множеством птиц и
множеством зверей (приводятся несколько
примеров). В качестве пустого множества можно
дать такой пример: в яркий солнечный день на небе
нет облаков, поэтому в этот день множество
облаков (такое множество естественно существует)
– пустое, а в другой день оно уже не будет пустым.
Этот пример используется в тетради А.В. Горячева
“Информатика в играх и задачах” 3 класс, часть 2.
Можно привести и другие примеры, когда какое-то
множество в конкретной ситуации будет пустым.

Также для удобства выполнения различных
заданий необходимо ввести систему обозначения
множеств (геометрические фигуры), подчеркнув,
что это только условное обозначение, но оно очень
удобно. Элементы множеств обозначаются точками.

Для закрепления понятия “элементы множества”
учащимся предлагается следующее задание 1 (приложение 2) (его можно давать
как домашнее задание, которое вклеивается в
тетрадь).

2. Далее вводятся понятия, связанные с
использованием логических связок в названиях
множеств.

В названиях множеств и высказываниях могут
употребляться логические связки: “и”, “не”,
“или” и их комбинация: “не … и”, “не …
или”. “не … и не …”

Если в названии множества есть связка “не”,
то его элементы находятся за пределами фигуры,
обозначающей это множество.

Если в названии множества есть связка “и”,
то его элементы находятся на пересечении фигур,
обозначающих множества.

Если в названии множества есть связка “или”,
то это означает, что его элементы находятся в
нескольких фигурах.

Эти схемы также необходимо закрепить с
учащимися на разных примерах, включенных в
задания в тетради (курс Горячева для начальной
школы), а также на тех, где они сами приводят
примеры различных множеств. Для закрепления
понятий пересечения и объединения множеств
учащимся предлагается дополнительное задание 2.

3. На следующем(их) уроке(ах) следует продолжить
подробный разбор заданий, например, включив
задания на пересечение трех множеств. (Желательно
также, чтобы эти схемы были зарисованы учащимися
в тетрадях).

При пересечении 2-х множеств образуется IV
области: 2 области без пересечения, одна область
пересечения множеств и одна область, лежащая за
пределами выделенных множеств.

При пересечении 3-х множеств образуется VIII
областей: 3 области без пересечения, 4 области
пересечения множеств и 1 область, лежащая за
пределами выделенных множеств.

Обозначение множеств:

При пересечении двух множеств
закрашивается вся область пересечения этих
множеств. При объединении двух множеств
закрашиваются оба множества. При пересечении
трех множеств закрашивается общая часть всех
трех множеств. При отрицании всех трех
множеств закрашивается область, не включающая в
себя сами множества.

Данные схемы сделаны для задания, когда надо
распределить слова, в состав которых входят
буквы “С”, “Т” и “О”. Набор слов должен
включать слова только с “Т”, только с “С”,
только с “О”, а также одновременно с двумя и
тремя буквами. Два-три слова должны быть без букв
“С”, “Т”, “О”. (Например: рельсы, купе,
проводник, скорость, колесо, электровоз, тамбур,
вагон, сумка, место, шпалы, поезд, машинист, билет,
состав, дверь, станция).

В курсе информатики А.В. Горячева в тетради 2
класса есть аналогичное задание на множества
“Круглые”, “Желтые”, “Шары”.

Закрепление теоретического материала должно
сопровождаться решением задач. Простейшие
задачи, например, “Про коз и коров”, “Фиалки и
подруги”, “Газеты и журналы” могут быть
использованы даже во 2 классе (см. приложение
4). Для более сильных учеников и для более
старших классов, соответственно, можно подобрать
задачи нужного уровня, а можно также
использовать какие-то задачи и для проведения
конкурсов, КВНов, школьных олимпиад, недели
математики и информатики. Подобные задачи удобно
решать, используя схему множеств и обозначая
элементы просто точками (если числа малые) или
указывая число элементов в соответствующей
области (в пересечении, без пересечения).

Задачи собраны из самых различных источников,
включая журнал “1 сентября. Информатика”, сайт
Малого Мехмата МГУ и другие сайты, посвященные
решению логических задач.

• Приложение 1. Презентация
  “Множества”
• Приложение 2. Задание 1.
• Приложение 3. Задание 2.
• Приложение 4. Дополнительные
  задачи.

Список литературы.

1. Горячев А.В., Горина К.И., Суворова Н.И.
   “Информатика в играх и задачах” 2 кл., в 2-х ч.
2. Горячев А.В., Горина К.И., Суворова Н.И.
   “Информатика в играх и задачах” 3 кл., в 2-х ч.
3. Горячев А.В., Горина К.И., Суворова Н.И.
   “Информатика в играх и задачах” 4 кл., в 2-х ч.
4. Горячев А.В., Горина К.И., Суворова Н.И.
   Методические рекомендации для учителя. 2 кл..
5. Горячев А.В., Горина К.И., Суворова Н.И.
   Методические рекомендации для учителя. 3 кл..
6. Горячев А.В., Горина К.И., Суворова Н.И.
   Методические рекомендации для учителя. 4 кл.
7. Горячев А.В., Суворова Н.И. Информатика. Логика и
   алгоритмы. 3 кл.
8. Горячев А.В., Суворова Н.И. Информатика. Логика и
   алгоритмы. 4 кл.
9. Журнал “1 сентября. Информатика”. Сайт https://inf.1sept.ru/
10. Фестиваль “Открытый урок”. Сайт https://urok.1sept.ru/ раздел
    “Информатика”.
11. Малый Мехмат МГУ. Сайт http://mmmf.msu.ru/.
12. Сайт Логические задачи и головоломки http://www.smekalka.pp.ru/.
13. Сайт Логические задачи, головоломки, загадки,
    тесты – Лого-рай http://logo-rai.ru/

Множество — это коллекция, которая реализует основные математические операции над множествами: пересечения (intersection), объединение (union), разность (difference) и симметрическая разность (symmetric difference). Каждый из алгоритмов мы разберем в соответствующем разделе.

Также смотрите другие материалы этой серии: бинарное дерево, стеки и очереди, динамический массив, связный список, оценка сложности алгоритма и сортировка.

Множество

В математике множества — это коллекции объектов, у которых есть что-то общее. Например, мы можем объявить множество четных положительных целых чисел:

[2, 4, 6, 8, 10, ...]

Или множество нечетных положительных целых:

[1, 3, 5, 7, 9, ...]

В этих двух множествах нет общих элементов. Давайте теперь посмотрим на множество делителей числа 100:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

Теперь мы можем узнать, какие делители числа 100 — нечетные, просто глядя на множество нечетных чисел и на множество делителей и выбирая те из чисел, которые присутствуют в обоих. Мы также можем ответить на вопрос: «Какие нечетные числа не являются делителями ста?» или «Какие положительные целые, четные или нечетные, не являются делителями ста?».

На первый взгляд это кажется не очень полезным, но это искусственный пример. Предположим, что у нас есть множество всех работников предприятия и множество работников, прошедших ежемесячную проверку. Тогда мы с легкостью сможем ответить на вопрос: «Кто из работников не прошел проверку?».

Мы также можем добавить различные множества и построить более сложный запрос, например: «Кто из штатных работников отдела продаж, имеющих корпоративную кредитную карточку, не прошел обязательный курс повышения квалификации?».

Класс Set

Класс Set реализует интерфейс IEnumerable и принимает аргумент типа, который является наследником IComparable, так как для работы алгоритмов нужна проверка элементов на равенство.

Элементы нашего множества будут храниться в экземпляре стандартного класса .NET List, но на практике для хранения обычно используются древовидные структуры, например, двоичное дерево поиска. Выбор внутреннего представления будет влиять на сложность алгоритмов работы с множеством. К примеру, при использовании списка метод Contains будет выполняться за O(n) времени, в то время как множество, реализованное с помощью дерева, будет работать в среднем за O(log n) времени.

Кроме методов для работы с множеством класс Set также имеет конструктор, который принимает IEnumerable с начальными элементами.

public class Set : IEnumerable
    where T: IComparable
{
    private readonly List _items = new List();
 
    public Set()
    {
    }
 
    public Set(IEnumerable items)
    {
        AddRange(items);
    }
 
    public void Add(T item);
 
    public void AddRange(IEnumerable items);
 
    public bool Remove(T item);
 
    public bool Contains(T item);
 
    public int Count
    {
        get;
    }
 
    public Set Union(Set other);
 
    public Set Intersection(Set other);
 
    public Set Difference(Set other);
 
    public Set SymmetricDifference(Set other);
 
    public IEnumerator GetEnumerator();
 
    System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator();
}

Метод Add

• Поведение: Добавляет элементы в множество. Если элемент уже присутствует в множестве, бросается исключение InvalidOperationException.
• Сложность: O(n)

При реализации метода Add необходимо решить, будем ли мы разрешать дублирующиеся элементы. К примеру, если у нас есть мнжество:

[1, 2, 3, 4]

Если пользователь попытается добавить число 3, в результате получится:

[1, 2, 3, 3, 4]

В некоторых случаях это допустимо, но в нашей реализации мы не будем поддерживать дубликаты. Если представить, например, множество студентов колледжа, было бы нелогичным добавлять в него одного и того же студента дважды. На самом деле, попытка добавить элемент, который уже присутствует — скорее всего ошибка, и наша реализация класса Set воспринимает ее именно так.

Метод Add использует метод Contains, который будет рассмотрен далее.

public void Add(T item)
{
    if (Contains(item))
    {
        throw new InvalidOperationException(
"Item already exists in Set"
);
    }
 
    _items.Add(item);
}

Метод AddRange

• Поведение: Добавляет несколько элементов в множество. Если какой-либо из добавляемых элементов присутствует в множестве, или в добавляемых элементах есть дублирующиеся, выбрасывается исключение InvalidOperationException.
• Сложность: O(m·n), где m — количество вставляемых элементов и n — количество элементов множества.

public void AddRange(IEnumerable items)
{
    foreach (T item in items)
    {
        Add(item);
    }
}

Метод Remove

• Поведение: Удаляет указанный элемент из множества и возвращает true. В случае, если элемента нет, возвращает false.
• Сложность: O(n)

public bool Remove(T item)
{
    return _items.Remove(item);
}

Метод Contains

• Поведение: Возвращает true, если множество содержит указанный элемент. В противном случае возвращает false.
• Сложность: O(n)

public bool Contains(T item)
{
    return _items.Contains(item);
}

Метод Count

• Поведение: Возвращает количество элементов множества или 0, если множество пусто.
• Сложность: O(1)

public int Count
{
    get
    {
        return _items.Count;
    }
}

Метод GetEnumerator

• Поведение: Возвращает итератор для перебора элементов множества.
• Сложность: Получение итератора — O(1), обход элементов множества — O(n).

public IEnumerator GetEnumerator()
{
    return _items.GetEnumerator();
}
 
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return _items.GetEnumerator();
}

Алгоритмы

Метод Union

• Поведение: Возвращает множество, полученное операцией объединения его с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Объединение множеств — это множество, которое содержит элементы, присутствующие хотя бы в одном из двух.

Например, есть два множества (выделены красным):

При операции объединения выбираются элементы обоих множеств. Если элемент присутствует в обоих множествах, берется только одна его копия. Объединение двух множеств показано желтым цветом.

Такая диаграмма, наглядно показывающая операции над множествами, называется диаграммой Венна.

Другой пример с использованием множеств целых чисел:

[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]

public Set Union(Set other)
{
    Set result = new Set(_items);
 
    foreach (T item in other._items)
    {
        if (!Contains(item))
        {
            result.Add(item);
        }
    }
 
    return result;
}

Метод Intersection

• Поведение: Возвращает множество, полученное операцией пересечения его с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Пересечение множеств содержит только те элементы, которые есть в обоих множествах. Используя диаграмму Венна, пересечение можно изобразить так:

Или, используя целые числа:

[1, 2, 3, 4] intersect [3, 4, 5, 6] = [3, 4]

public Set Intersection(Set other)
{
    Set result = new Set();
 
    foreach (T item in _items)
    {
        if (other._items.Contains(item))
        {
            result.Add(item);
        }
    }
 
    return result;
}

Метод Difference

• Поведение: Возвращает множество, являющееся разностью текущего с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Разность множеств — это все элементы, которые содержатся в одном множестве (том, у которого вызывается метод), но не содержатся в другом (том, которое передается аргументом). Диаграмма Венна для разности множеств будет выглядеть так:

Или, используя целые числа:

[1, 2, 3, 4] difference [3, 4, 5, 6] = [1, 2]

public Set Difference(Set other)
{
    Set result = new Set(_items);
 
    foreach (T item in other._items)
    {
        result.Remove(item);
    }
 
    return result;
}

Метод Symmetric Difference

• Поведение: Возвращает множество, являющееся симметрической разностью текущего с указанным.
• Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.

Симметрическая разность — это все элементы, которые содержатся только в одном из рассматриваемых множеств. Диаграмма Венна для симметрической разности будет выглядеть так:

Или, используя целые числа:

[1, 2, 3, 4] symmetric difference [3, 4, 5, 6] =
[1, 2, 5, 6]

Вы, возможно, заметили, что симметрическая разность — это «пересечение наоборот». Учитывая это, давайте попробуем найти ее, используя уже имеющиеся операции.

Итак, мы хотим получить множество, которое содержит все элементы из двух множеств, за исключением тех, которые есть в обоих. Другими словами, мы хотим получить разность объединения двух множеств и их пересечения.

Или, если рассматривать по шагам:

[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]

[1, 2, 3, 4] intersection [3, 4, 5, 6] = [3, 4]

[1, 2, 3, 4, 5, 6] set difference [3, 4] = [1, 2, 5, 6]

Что дает нам нужный результат: [1, 2, 5, 6].

public Set SymmetricDifference(Set other)
{
    Set union = Union(other);
    Set intersection = Intersection(other);
 
    return union.Difference(intersection);
}

Метод IsSubset

Вы, возможно, интересуетесь, почему мы не добавили метод IsSubset, который проверяет, содержится ли одно множество целиком в другом. Например:

[1, 2, 3] is subset [0, 1, 2, 3, 4, 5] = true

В то время, как:

[1, 2, 3] is subset [0, 1, 2] = false

Дело в том, что эту проверку можно провести, используя имещиеся методы. К примеру:

[1, 2, 3] difference [0, 1, 2, 3, 4, 5] = []

Пустое множество в результате говорит нам о том, что все элементы первого множества содержатся во втором, а значит, первое является подмножеством второго. Другой способ проверить это:

[1, 2, 3] intersection [0, 1, 2, 3, 4, 5] =
[1, 2, 3]

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

В общем случае, конечно, класс Set может иметь метод IsSubset (который может быть реализован более эффективно). Однако стоит помнить, что это уже не какая-то новая возможность, а просто другое применение существующих.

Продолжение следует

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

_{Перевод статьи «The Set Collection»}

Множественный тип данных

Множество в языке Паскаль – это ограниченный набор различных элементов одного (базового) типа , которые рассматриваются как единое целое.

Базовый тип

• это совокупность значений, из которых могут быть образованы множества. В качестве базового типа может быть использован любой тип, кроме вещественного.

Значение переменной множественного типа может содержать любое количество различных элементов базового типа – от нуля элементов (пустое множество) до всех возможных значений базового типа (всего может быть не более 256 различных элементов).

Описание

• В разделе описания типов:

Type = set of ;

Var : ;

• В разделе описания переменных:

Var : set of ;

• Пример :

Type mnog_char = set of char;

Var mn1: mnog_char;

mn2: set of char;

mn3: set of ‘A’..’Z’;

s1: set of byte;

s2: set of 1000 .. 1200;

Формирование множеств

В программе элементы множества задаются в квадратных скобках, через запятую. Если элементы идут подряд друг за другом, то можно использовать диапазон.

• Пример:

Type digit = set of 1..5;

Var s: digit;

Переменная s может принимать значения, состоящие из любой совокупности целых чисел от 1 до 5:

[ ] – пустое множество;

[1], [2], [3], [4], [5] – одноэлементные множества;

[1,2],…[4,5] – двухэлементные; [1, 2, 3] – трехэлементное;

[1, 2, 3, 4],… [2, 3, 4, 5] – четырехэлементные;

[1, 2, 3, 4, 5] – полное множество (взяты все элементы базового типа)

Операции над множествами

• Объединением двух множеств называется множество элементов, принадлежащих обоим множествам. Знак операции – « + ».

• Примеры:

• [‘A’, ’F’] + [‘B’, ’D’] = [‘A’,’F’,‘B’, ’D’];
• [1..3, 5, 7, 11] + [3..8,10, 12, 15..20] = [1..8, 10..12, 15..20];
• A1:=[‘a’, .. ‘z’]; A1:= A1 + [‘A’]; – к множеству A1 добавляем элемент. Тогда A1 = [‘A’, ‘a’ .. ‘z’];

А + В

В

А

Операции над множествами

Пересечением двух множеств называется множество элементов, принадлежащих одновременно и первому, и второму множеству, т.е. это общие элементы. Знак операции – « * ».

• Примеры:

• [‘A’, ’F’] * [‘B’, ’D’] =[ ] – так как общих элементов нет ;
• [1..3, 5, 7, 11] * [3..8,10, 12, 15..20] = [ 3, 5, 7 ];
• S1:=[1 .. 5, 9]; S2:= [3 .. 7, 12]; S:= S1 * S2;

то результат выполнения S =[3 .. 5];

Операции над множествами

Вычитанием двух множеств называется множество, состоящее из тех элементов первого множества, которые не являются элементами второго множества. Знак операции – « – ».

• Примеры:

• [‘A’, ’F’] – [‘B’, ’D’] =[‘A’, ‘F’ ] – так как общих элементов нет ;
• [1..3, 5, 7, 11] – [3..8,10, 12, 15..20] = [1 .. 2, 11];
• S1:=[1 .. 5, 9]; S2:= [3 .. 7, 12]; S:= S1 – S2;

то результат выполнения S =[1 .. 2, 9];

true , т.к 5 принадлежит [3 .. 7]; ‘ a’ in [‘A’ ..’Z’] = false , т.к. маленькой латинской буквы ‘a’ нет среди больших латинских букв. Примечание. Оператор вида: if (ch=‘a’) or (ch=‘b’) or (ch=‘x’) or (ch=‘y’) then s; может быть переписан в компактной наглядной форме: if ch in [‘a’,’b’,’x’,’y’] then s; ” width=”640″

Операция определения принадлежности элемента множеству

in – служебное слово. Логическая операция имеет результат true , если значение входит в множество и false в противном случае.

• Примеры:

5 in [3 .. 7] = true , т.к 5 принадлежит [3 .. 7];

‘ a’ in [‘A’ ..’Z’] = false , т.к. маленькой латинской буквы ‘a’ нет среди больших латинских букв.

Примечание. Оператор вида:

if (ch=‘a’) or (ch=‘b’) or (ch=‘x’) or (ch=‘y’) then s;

может быть переписан в компактной наглядной форме: if ch in [‘a’,’b’,’x’,’y’] then s;

. Результат – true или false . A ≤ B true true false A false true false ” width=”640″

Сравнение множеств

Используются операции отношения:

= , , =, . Результат – true или false .

A ≤ B

true

true

false

A

false

true

false

• Пример

Составить программу выделения из множества целых чисел от 1 до 30 следующих множеств:

• множества чисел кратных 2;
• множества чисел кратных 3;
• множества чисел кратных 6;
• множества чисел кратных 2 или 3;

Вопросы:

• Сколько множеств надо описать? Какого они типа?
• Какое первоначальное значение множеств?
• Как формируются множества?
• Как осуществить вывод сформированных множеств?

• 4 множества типа byte
• – пустое множество
• Первые два – перебором всех чисел данного промежутка и занесением необходимых, третье и четвертое – из первых двух путем применения операций пересечения и объединения
• Вывод делается только поэлементно, поэтому удобно составить процедуру, которой передается множество, элементы которого и будут выдаваться на экран. Для этого в разделе типов надо создать тип множества и его использовать в дальнейшем.

program Ex1;

const n=30;

type mn=set of 1..n;

var n2,n3,n6,n23: mn; {n2 – множество чисел кратных 2, } { n3 – кратных 3}

k:integer; { n6 – кратных 6, n23 – кратных 2 или 3}

procedure Print(m:mn);

var i:integer;

Begin

for i:=1 to n do If i in m then write(i:3);

writeln;

end;

begin

n2:=[ ]; n3:=[ ]; {начальное значение множества}

for k:=1 to n do { формирование n2 и n3}

begin

if k mod 2=0 then n2:=n2+[k];

if k mod 3=0 then n3:=n3+[k]

end;

n6:=n2*n3;{числа кратные 6, это те, которые кратны и 2, и 3 ,} { поэтому это пересечение двух первых множеств}

n23:=n2+n3; {а числа кратные 2 или 3 – это объединение этих же множеств}

writeln(‘числа, кратные 2′); print(n2);

writeln(‘ числа, кратные 3’); print(n3);

writeln(‘ числа, кратные 6’); print(n6);

writeln(‘ числа, кратные 2 или 3’); print(n23);

readln;

end.

Задание.

Изменить программу так, чтобы результатом ее работы являлось множество чисел, делящихся на 3, но не делящихся на 2.

Задача.

Дано натуральное число n .составить программу, печатающую все цифры, не входящие в десятичную запись данного натурального числа в порядке возрастания.

program ex3;

type mn=set of 0..9;

var s:mn; n:longint; l,k:integer;

begin

write(‘Введите число N ‘); readln(n);

s:=[ ]; { формирование множества цифр десятичной записи числа   n }

while n0 do

begin

k:=n mod 10; n:=n div 10;

if not (k in s) then s:=s+[k];

end;

{ вывод цифр в порядке возрастания}

for k:=0 to 9 do

if not (k in s) then write(k:2);

writeln;

readln

end.

Другие задачи

Множества в Python – это структура данных, которые содержат неупорядоченные элементы. Элементы также не является индексированным. Как и список, множество позволяет внесение и удаление элементов. Однако, есть ряд особенных характеристик, которые определяют и отделяют множество от других структур данных:

• Множество не содержит дубликаты элементов;
• Элементы множества являются неизменными (их нельзя менять), однако само по себе множество является изменяемым, и его можно менять;
• Так как элементы не индексируются, множества не поддерживают никаких операций среза и индексирования.

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

Содержание:

• Создание множеств
• Доступ к элементам множеств
• Добавление элементов во множество
• Удаление элементов из множеств
• Объединение множеств
• Пересечение множеств
• Разница множеств
• Сравнение множеств
• Методы множеств
• Frozenset в Python
• Вывод

Создание множеств

Существует два пути, следуя которым, мы можем создавать множества в Python.

Мы можем создать множество путем передачи всех элементов множества внутри фигурных скобок {} и разделить элементы при помощи запятых (,). Множество может содержать любое количество элементов и элементы могут быть разных типов, к примеру, целые числа, строки, кортежи, и т. д. Однако, множество не поддерживает изменяемые элементы, такие как списки, словари, и так далее.

Рассмотрим пример создания множества в Python:

Результат:

Только что мы создали множество чисел. Мы также можем создать множество из строк. Например:

Результат:

Возможно вы обратили внимание на то, что элементы в выдаче выше находятся в другом порядке, отличном от того, как мы добавляли их в множество. Это связано с тем, что элементы множества находятся в произвольном порядке. Если вы запустите тот же код еще раз, возможно вы получите выдачу с элементами, которые каждый раз будут находиться в другом порядке.

Мы также можем создать множество с элементами разных типов. Например:

Результат:

Все элементы в упомянутом выше множестве принадлежат разным типам.

Мы также можем создать множество из списков. Это можно сделать, вызвав встроенную функцию Python под названием set(). Например:

Результат:

Как упоминалось ранее, множества не содержат дубликаты элементов. Предположим, наш список содержит дубликаты элементов, как показано ниже:

Результат:

Множество удалило дубликаты и выдало только по одному экземпляру элементов. Это также происходит при создании множества с нуля. Например:

Результат:

И снова, множество удалило дубликаты и вернуло только один из дублируемых объектов.

Создание пустого множества подразумевает определенную хитрость. Если вы используете пустые фигурные скобки {} в Python, вы скорее создадите пустой словарь, а не множество. Например:

Результат:

Как показано в выдаче, тип переменной х является словарем.

Чтобы создать пустое множество в Python, мы должны использовать функцию set() без передачи какого-либо значения в параметрах, как показано ниже:

Результат:

Выдача показывает, что мы создали множество.

Доступ к элементам множеств

Python не предоставляет прямой способ получения значения к отдельным элементам множества. Однако, мы можем использовать цикл для итерации через все элементы множества. Например:

Результат:

Мы также можем проверить наличие элемента во множестве при помощи in, как показано ниже:

Результат:

Код возвращает «True«, а это означает, что элемент был найден во множестве. Аналогичным образом, при поиске элемента, который отсутствует во множестве, мы получим «False«, как показано ниже:

Как и ожидалось, код вернул «False«.

Добавление элементов во множество

Python позволяет нам вносить новые элементы во множество при помощи функции add(). Например:

Результат:

Элемент «Feb» успешно внесен во множество. Если это было множество чисел, мы не можем передать новый элемент внутри скобочек, как мы делаем это для строк. Например:

Результат:

В следующем разделе мы обсудим, как удалять элементы из множеств.

Удаление элемента из множеств

Python позволяет нам удалять элемент из множества, но не используя индекс, так как множество элементов не индексированы. Элементы могут быть удалены при помощи обоих методов discard() и remove().

Помните, что метод discard() не будет выдавать ошибку, если элемент не был найден во множестве. Однако, если метод remove() используется и элемент не был найден, возникнет ошибка.

Давайте продемонстрируем как удалять элемент при помощи метода discard():

Результат:

Элемент 3 был удален из множества.

Аналогично, метод remove() может использоваться следующим образом:

Результат:

Теперь попробуем удалить элемент, которого нет во множестве. Сначала используем метод discard():

Результат:

Выдача выше показывает, что никакого воздействия на множество не было оказано. Теперь посмотрим, что выйдет из использования метода remove() по аналогичному сценарию:

Результат:

Выдача показывает, что метод выдал ошибку KeyError, так как мы пытались удалить элемент, которого нет во множестве.

С методом pop(), мы можем удалить и вернуть элемент. Так как элементы находятся в произвольном порядке, мы не можем утверждать или предсказать, какой элемент будет удален.

Например:

Результат:

Вы можете использовать тот же метод при удалении элемента и возврате элементов, которые остаются во множестве. Например:

Результат:

Эти элементы остаются во множестве.

Метод Python под названием clear() поможет удалить все элементы во множестве. Например:

Результатом является пустой set() без каких-либо элементов внутри.

Объединение множеств

Предположим, у нас есть два множества, А и В. Объединение этих двух множеств — это множество со всеми элементами обеих множеств. Такая операция выполняется при помощи функции Python под названием union().

Рассмотрим пример:

Результат:

Объединение может состоять из более чем двух множеств, и все их элементы сложатся в одно большое множество. Например:

Результат:

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

Результат:

Оператор | может также использоваться при поиске объединения двух или более множеств. Например:

Результат:

Если вы хотите создать объединение из более двух множеств, разделите названия множеств при помощи оператора | . Взглянем на пример:

Результат:

Пересечение множеств

Предположим, у вас есть два множества: А и В. Их пересечение представляет собой множество элементов, которые являются общими для А и для В.

Операция пересечения во множествах может быть достигнута как при помощи оператора &, так и метода intersection(). Рассмотрим пример:

В обеих множествах 3 является общим элементом. То же самое может быть достигнуто при использовании метода intersection():

В следующем разделе мы обсудим, как определить разницу между множествами.

Разница между множествами

Предположим, у вас есть два множества: А и В. Разница между А и В (А — В) — это множество со всеми элементами, которые содержатся в А, но не в В. Соответственно, (В — А) — это множество со всеми элементами в В, но не в А.

КОД

Для определения разницы между множествами в Python, мы можем использовать как функцию difference(), так и оператор — . Рассмотрим пример:

Результат:

В показанном выше скрипте, только первые три элемента множества set_a отсутствуют во множестве set_b, формируя нашу выдачу. Оператор минус - можно также применить для нахождения разницы между двумя множествами, как показано ниже:

Результат:

Симметричная разница между множествами А и В — это множество с элементами, которые находятся в А и В, за исключением тех элементов, которые являются общими для обеих множеств. Это определяется использованием метода Python под названием symmetric_difference(), или оператора ^. Посмотрим на пример:

Результат:

Симметричную разницу можно также найти следующим образом:

Результат:

Сравнение множеств

Мы можем сравнить множества в зависимости от того, какие элементы в них содержатся. Таким образом, мы можем сказать, является ли множество родительским, или дочерним от другого множества. Результат такого сравнения будет либо True, либо False.

Чтобы проверить, является ли множество А дочерним от В, мы можем выполнить следующую операцию:

Чтобы узнать является ли множество В дочерним от А, мы можем выполнить следующую операцию, соответственно:

Например:

Результат:

Дочернее и родительское множество может также быть проверено при помощи методов issubset() и issuperset(), как показано ниже:

Результат:

В следующем разделе мы обсудим некоторые из наиболее часто используемых методов для манипуляции множествами, предоставленных в Python, которые мы не успели упомянуть.

Методы множеств

Python содержит огромное количество встроенных методов, включая следующие:

Метод copy()

Этот метод возвращает копию множества. Например:

Результат:

Выдача показывает, что х является копией множества string_set.

Метод isdisjoint()

Этот метод проверяет, является ли множество пересечением или нет. Если множества не содержат общих элементов, метод возвращает True, в противном случае — False. Например:

Результат:

Оба множества не имеют общих элементов, что делает выдачу True.

Метод len()

Этот метод возвращает длину множества, которая является общим количеством элементов во множестве. Пример:

Выдача показывает, что длина множества является 4.

Frozenset в Python

Frozenset (замороженное множество) – это класс с характеристиками множества, однако, как только элементы становятся назначенными, их нельзя менять. Кортежи могут рассматриваться как неизменяемые списки, в то время как frozenset-ы — как неизменные множества.

Множества являются изменяемыми и нехешируемыми, это значит, что мы не можем использовать их как словарные ключи. Замороженные множества (frozenset) являются хешированными и могут использоваться в качестве ключей словаря.

Для создания замороженного множества, мы используем метод frozenset(). Давайте создадим два замороженных множества, Х и Y:

Результат:

Замороженные множества поддерживают использование множественных методов Python, таких как copy(), difference(), symmetric_difference(), isdisjoint(), issubset(), intersection(), issuperset() и union().

Вывод

Данная статья предоставляет подробное введение во множества языка программирования Python. Математическое определение множеств аналогично определению множеств в Python.

Множество — это набор элементов в произвольном порядке. Само по себе, множество является изменяемым, однако его элементы являются неизменяемыми.

Однако, мы можем добавлять и убирать элементы из множества без каких-либо проблем. В большей структур данных элементы являются индексированными. Однако, элементы множеств не являются индексированными. Это делает невозможным для нас выполнять операции, которые направлены на определенные элементы множества.

Мы знаем довольно много о структурах данных, понимаем их устройство, разбираемся, какие структуры работают быстро и помогают решать конкретные задачи. Но эти знания бесполезны, если мы не понимаем, как это использовать в реальной жизни. Это похоже на изучение геометрии в школе. Вы долго считаете предмет бесполезным, пока однажды не появляется необходимость рассчитать площадь пола, чтобы заказать новое ковровое покрытие. Впрочем, пользу геометрии можно почувствовать, даже если вы никогда не считали площадь пола в комнате самостоятельно.

• Теория множеств без страха
• Об операциях с множествами без боли
• Множества вокруг нас
• Заключение

Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.

Теория множеств без страха

Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.

Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.

Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.

В этом определении есть три важных слова: «неупорядоченная», «дублирующихся» и «элементов». Эти слова точно передают суть и устройство множества. Если мы это запомним, то будем знать основную информацию о том, как работает эта структура данных.

Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.

---

Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.

Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.

---

Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.

Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.

Об операциях с множествами без боли

Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.

---

Пересечение множеств часто записывается с помощью такой нотации: X ∩ Y. Пересечение определяет, где два множества пересекаются. Другими словами, эта операция возвращает все элементы, которые входят в два множества. В нашем примере пересечение Set X и Set Y возвращает все книги, которые человек читал и которые есть у него дома. Хороший ключ к пониманию пересечения — ключевое слово «и». Мы получаем книги, которые человек читал и которые есть у него дома. Несмотря на то, что полученные с помощью пересечения книги существуют в двух множествах, мы не повторяем их, так как в множестве могут быть только уникальные элементы.

Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.

С помощью диаграммы Венна пересечение и объединение можно представить так:

---

Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.

Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.

---

Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X Y. Относительное дополнение X Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.

По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?

Вы могли заметить, что в части примеров мы имеем дело со строками, в другой части в качестве элементов выступают буквы и числа. Здесь надо подчеркнуть важный момент: множество может включать любой тип элементов или объектов. Вы можете рассматривать множества как хэши: они включают любые сущности, если те встречаются во множестве только один раз.

Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.

В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?

Правильное название для этого кейса — симметрическая разность множеств. Также употребляют термины «дизъюнктивное объединение» и «несвязное объединение». Симметрическая разность возвращает все элементы, которые входят в одно из множеств, но не входят в пересечение этих множеств. Пример на иллюстрации поможет разобраться с дизъюнктивным объединением.

---

В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).

Но не дайте сбить себя с толку!

Читайте также:
Что такое JVM? Знакомство с виртуальной машиной Java.

Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.

В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.

Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.

Множества вокруг нас

К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.

Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.

Вот пример на JavaScript.

var s = new Set();

s.add(2); 
// Set { 2}
s.add(45); 
// Set { 2, 45}
s.add(45); 
// Set { 2, 45}
s.add('hello world!'); 
// Set { 2, 45, 'hello world!' }

s.has(2); 
// true
s.has('cats'); 
// false

s.size; 
// 3

s.delete(45); 
// Set { 2, 'hello world!' }

s.has(45);    
// false

Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.

Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?

---

Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.

Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.

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

Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.

Читайте также
Haskell — язык, позволяющий глубже понять программирование. Как он устроен и почему его выбирают разработчики?

Заключение

Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.

Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.

Никогда не останавливайтесь:
В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.