Составление лексикографических сочетаний с повторениями — различия между версиями

Материал из ALL
Перейти к: навигация, поиск
(Новая страница: «'''Составление лексикографических перестановок с повторениями''' — это алгоритм (комбин…»)
 
Строка 1: Строка 1:
−
'''Составление лексикографических перестановок с повторениями''' — это алгоритм ([[комбинаторика|комбинаторная]] операция) получения перестановок с повторениями в лексикографическом порядке.  
+
'''Составление лексикографических сочетаний с повторениями ''' — это алгоритм ([[комбинаторика|комбинаторная]] операция) получения сочетаний с повторениями в лексикографическом порядке.  
 
== Обозначения ==
 
== Обозначения ==
 
Введём обозначения:
 
Введём обозначения:
  
−
'''k''' – число элементов конечного множества;
+
'''n''' – число элементов конечного множества;
  
−
'''n''' – число всех элементов с учётом повторений;
+
'''k''' – число элементов в сочетании и число возможных повторений;
  
−
'''m<sub>i</sub>''' – число повторений '''i'''-го элемента;
+
'''t''' – порядковый номер сочетания;
  
−
'''t''' – порядковый номер перестановки с повторениями;
+
'''{C<sub>1</sub>,C<sub>2</sub>,…,C<sub>k</sub>}''' – сочетание с повторениями '''k''' номеров элементов множества из '''n''' элементов.
 +
== Алгоритм сочетаний с повторениями ==
 +
Входные данные: '''n, k'''.
  
−
'''{P<sub>1</sub>,P<sub>2</sub>,…,P<sub>n</sub>}''' – перестановка из '''n''' номеров элементов.
+
[[файл:КОМ72.JPG]]
−
== Алгоритм перестановок с повторениями ==
+
−
Входные данные: '''n; k; {m<sub>1</sub>,m<sub>2</sub>,…,m<sub>k</sub>}'''.
+
−
 
+
−
[[файл:КОМ62.JPG]]
+
 
=== Пример ===
 
=== Пример ===
−
При '''n=5; k=3''' получаем 20 перестановок с повторениями:
+
При '''n=5, k=3''' получаем 35 сочетаний:
  
−
[[файл:КОМ64.JPG]]
+
[[файл:КОМ74.JPG]]
 
== Другие алгоритмы: ==
 
== Другие алгоритмы: ==
 
*[[составление перестановок]];
 
*[[составление перестановок]];
Строка 33: Строка 31:
 
*[[составление лексикографических разбиений]];
 
*[[составление лексикографических разбиений]];
 
*[[составление следующего разбиения]];
 
*[[составление следующего разбиения]];
−
*[[составление распределений]];
 
 
*[[составление лексикографических распределений]];
 
*[[составление лексикографических распределений]];
−
*[[составление следующего распределения]];
+
*[[составление следующего распределения]].
−
*[[составление лексикографических перестановок с повторениями]];
+
−
*[[составление следующей перестановки с повторениями]];
+
−
*[[составление лексикографических сочетаний с повторениями]].
+
 
== Ссылки ==
 
== Ссылки ==
 
* [[Участник:Logic-samara]]  
 
* [[Участник:Logic-samara]]  
 
[[Категория:Дискретная математика]][[Категория:Алгоритмы]][[Категория:Комбинаторика]]
 
[[Категория:Дискретная математика]][[Категория:Алгоритмы]][[Категория:Комбинаторика]]

Версия 20:16, 5 марта 2016

Составление лексикографических сочетаний с повторениями — это алгоритм (комбинаторная операция) получения сочетаний с повторениями в лексикографическом порядке.

Обозначения

Введём обозначения:

n – число элементов конечного множества;

k – число элементов в сочетании и число возможных повторений;

t – порядковый номер сочетания;

{C1,C2,…,Ck} – сочетание с повторениями k номеров элементов множества из n элементов.

Алгоритм сочетаний с повторениями

Входные данные: n, k.

КОМ72.JPG

Пример

При n=5, k=3 получаем 35 сочетаний:

КОМ74.JPG

Другие алгоритмы:

Ссылки

Источник — «https://allll.net/w/index.php?title=Составление_лексикографических_сочетаний_с_повторениями&oldid=36365»