Учебно-методическое пособие. Алматы, 2017 ббк
Размещения с повторениями
жүктеу/скачать 483.39 Kb.
|
| Размещения с повторениями. До сих пор рассматривались соединения, в каждое из которых любой из n различных элементов входит один раз. Можно рассматривать соединения с повторениями, т. е. соединения, в каждом из которых любой из n различных элементов может входить более одного раза.
Размещения из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в каждом размещении любое число раз, но не более чем m, называются размещениями из m элементов по n с повторениями. Пример. Выпишем размещения с повторениями из двух элементов а, b по три: ааa, aаb, aba, abb, baa, bab, bba, bbb. Количество размещений из N элементов по M с повторениями обозначают . Справедлива формула:
Действительно, на каждое из m мест мы можем поместить любой из n элементов. Опишем алгоритм генерации всех размещений из n элементов по m с повторениями. Пронумеруем элементы от 0 до n-1, и в дальнейшем будем работать не с самими элементами, а с их номерами. Каждому размещению можно сопоставить число в n-ичной системе счисления, состоящее из m цифр. Приведем фрагмент программы, генерирующей размещения с повторениями : For i:= 0 to m do А(i) :=0; while A(m)=0 do begin
i:=0; while A(i)=n – 1 do begin A(i) :=0; Inc(i); end;
Inc(А(i)); for i = m-1 downto 0 do A(i) :=А(i); end;
жүктеу/скачать 483.39 Kb. Достарыңызбен бөлісу:
|