Егор Долгов
Егор Долгов
(обновлено )
За все время: 2013 просмотров, 919 посетителей.
За последние 30 дней: 16 просмотров, 14 посетителей.

Комбинаторика (алгоритмы на языке Dart)

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

Число перестановок

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

В комбинаторике факториал натурального числа n интерпретируется как количество перестановок (упорядочиваний) множества из n элементов.


Число перестановок из 3 предметов.

Основные элементы кода программы "Алгоритм перестановки":

Пример вывода в консоль:

1 , 2 , 3
1 , 3 , 2
2 , 1 , 3
2 , 3 , 1
3 , 1 , 2
3 , 2 , 1
num: 6

Число расстановок (Размещения)

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


Число расстановок из 6 предметов на 3 места.

Следующий код отличается от предыдущего только новым списком list, в нем больше элементов.

Пример вывода в консоль (большая часть строк пропущена):

1 , 2 , 3
1 , 2 , 4
1 , 2 , 5
..............
6 , 5 , 3
6 , 5 , 4
num: 120

Число сочетаний

Сочетаниями из n элементов по m называются соединения, которые можно образовать из n элементов, собирая в каждое соединение m элементов; при этом соединения отличаются друг от друга только самими элементами (различие порядка их расположения во внимание не принимается).


Число сочетаний из 6 предметов по 3.

Код для сочетаний отличается от кода расстановок новыми начальными значениями для 2-го и 3-го цикла for.

Пример вывода в консоль

1 , 2 , 3
1 , 2 , 4
1 , 2 , 5
1 , 2 , 6
1 , 3 , 4
1 , 3 , 5
1 , 3 , 6
1 , 4 , 5
1 , 4 , 6
1 , 5 , 6
2 , 3 , 4
2 , 3 , 5
2 , 3 , 6
2 , 4 , 5
2 , 4 , 6
2 , 5 , 6
3 , 4 , 5
3 , 4 , 6
3 , 5 , 6
4 , 5 , 6
num: 20

Подборка заметок