Составление размещений — различия между версиями
Материал из ALL
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м |
||
| (не показано 27 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
'''Составление размещений''' — это алгоритм ([[комбинаторика|комбинаторная]] операция) получения упорядоченного определённым образом набора '''k''' номеров элементов множества, состоящего из '''n''' элементов. | '''Составление размещений''' — это алгоритм ([[комбинаторика|комбинаторная]] операция) получения упорядоченного определённым образом набора '''k''' номеров элементов множества, состоящего из '''n''' элементов. | ||
| + | == Обозначения == | ||
| + | '''n''' – число элементов конечного множества; | ||
| − | + | '''k''' – число элементов в размещении; | |
| − | + | ||
| − | ''' | + | |
'''t''' – порядковый номер размещения; | '''t''' – порядковый номер размещения; | ||
| Строка 11: | Строка 10: | ||
'''{A<sub>1</sub>,A<sub>2</sub>,…,A<sub>k</sub>}''' – размещение '''k''' номеров элементов множества из '''n''' элементов. | '''{A<sub>1</sub>,A<sub>2</sub>,…,A<sub>k</sub>}''' – размещение '''k''' номеров элементов множества из '''n''' элементов. | ||
| − | |||
== Алгоритм размещений == | == Алгоритм размещений == | ||
Входные данные: '''n, k'''. | Входные данные: '''n, k'''. | ||
[[файл:КОМ31.JPG]] | [[файл:КОМ31.JPG]] | ||
| − | + | * Заметим, что '''алгоритм размещений''' аналогичен '''[[Составление сочетаний|алгоритму сочетаний]]''' с добавлением к нему '''[[Составление перестановок|алгоритма перестановок]]'''. Просто в алгоритме сочетаний для каждого сочетания составляются все перестановки. | |
| − | == Пример | + | === Пример === |
При '''n=4, k=3''' получаем 24 размещения: | При '''n=4, k=3''' получаем 24 размещения: | ||
[[файл:КОМ33.JPG]] | [[файл:КОМ33.JPG]] | ||
| − | + | == [[Комбинаторные алгоритмы|Другие алгоритмы:]] == | |
| − | == Другие алгоритмы: == | + | {{Список КАлг}} |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Ссылки == | == Ссылки == | ||
| − | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
| − | [[Категория:Дискретная математика]] [[Категория:Алгоритмы]] | + | [[Категория:Дискретная математика]][[Категория:Комбинаторика]][[Категория:Алгоритмы]] |
Текущая версия на 10:41, 16 января 2024
Составление размещений — это алгоритм (комбинаторная операция) получения упорядоченного определённым образом набора k номеров элементов множества, состоящего из n элементов.
Обозначения
n – число элементов конечного множества;
k – число элементов в размещении;
t – порядковый номер размещения;
si – счётчик циклических сдвигов (i+1) номеров элементов;
{A1,A2,…,Ak} – размещение k номеров элементов множества из n элементов.
Алгоритм размещений
Входные данные: n, k.
- Заметим, что алгоритм размещений аналогичен алгоритму сочетаний с добавлением к нему алгоритма перестановок. Просто в алгоритме сочетаний для каждого сочетания составляются все перестановки.
Пример
При n=4, k=3 получаем 24 размещения:
