Другой варианта алгоритма генерации всех подмножеств. Сначала пример.
Дано множество из 5 элементов.
1 | [1, 2, 3, 4, 5] |
Возьмём пятизначное двоичное число и поставим в соответствие каждой цифре этого числа один из элементов исходного множества. Таким способом мы можем задавать подмножества исходного пятиэелементного множества.
1 2 3 | 10101 = [1, 3, 5] 00011 = [4, 5] 00000 = [] |
Читать далее Генерация всех подмножеств с помощью двоичного представления числа
Алгоритм взят из книги Теоретический минимум по Computer Science. Алгоритм итеративный и очень простой для понимания.
На изображении пример работы алгоритма для множества [1, 2, 3].
1 2 3 4 5 6 7 8 9 10 | результат = множество содержащие в себе пустое множество Для каждого элемента x из исходного множества копия_результата = копировать результат # в каждый элемент копии добавляем элемент исходного множества Для каждого элемента y из копия_результата y = y + x # Объединяем результат и копию результат = результат + копия_результата |
Каждый элемент исходного множества увеличивает результирующее множества в 2 раза. В итоге множество всех подмножеств будет содержать \(2^n\) элементов, где n — количество элементов исходного множества.
Пример на Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | import copy main_set = [1, 2, 3] print(main_set) def get_subsets(main): result = [[]] for main_element in main: new_set = copy.deepcopy(result) for item in new_set: item.append(main_element) result += new_set return result print(get_subsets(main_set)) |
Вместо
1 2 3 4 5 6 7 8 9 10 | if first_condition: if second_condition: first_operator else: second_operator else: if second_condition: second_operator else: first_operator |
можно записать
1 2 3 4 | if first_condition ^ second_condition: # ^ - оператор xor second_operator else first_operator |
Рассмотрим задачу похожую на игру Сапёр
Дано прямоугольное поле размером n на m. В поле каждая клетка обозначена либо символом точки ('.') точкой либо звёздочки ('*'). Точка означает пустое поле поле, звёздочка мину. Вывести на экран поле такого же размера где вместо точек указанна цифра - количество мин рядом с этой клеткой.
Далее описан способ перебора соседних клеток у определённой клетки для решения этой задачи. В двух вариантах: когда поле ограниченно, и когда неограниченно - клетка справа поля граничит с клеткой слева, клетки сверху граничат с клетками снизу. Похожий способ можно применять для сходных случаев перебора, например при переборе клеток шахматной доски куда может сходить конь.
Рассмотрим задачу
Дана строка с текстом, подсчитать количество появления разных букв в тексте.
Для хранения количества букв будем использовать словарь. Рассмотрим самый простой вариант подсчёта. Пройтись по всем буквам, если текущей буквы ещё нет в словаре, то это первое вхождение - устанавливаем кол-во равным одному, если буква уже есть то увеличиваем кол-во на 1.
Читать далее Группировка и подсчёт элементов в списке Python
Даны целые числа \(1 \leq n \leq 10^{18}\) и \(2 \leq m \leq 10^5\), необходимо найти остаток от деления n-го числа Фибоначчи на m.
Когда речь идёт о положительных числах то с операциями целочисленного деления и взятия остатка все довольно просто. Результат всегда положителен и удовлетворяет уравнению
\(div\) - целочисленное деление
\(mod\) - остаток от деления
\(r = (r\ div\ d) * d + (r\ mod\ d)\)
Если же делимое или делитель отрицательные то общая формула остается верной, но результаты отдельных операторов уже отличаются в зависимости от языка программирования.
