 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Алгоритм порождения разбиений
|
|
Как было сказано в разд. 1.1 разбиение можно интерпретировать как мультимножество { m 1· p 1, m 2· p 2,…, ml · pl,}. Например для n =7 все возможные разбиения представлены в табл.3.
Таблица 3
| № | Разбиение | № | Разбиение |
| {7·1} = {1,1,1,1,1,1,1} | {1·4,3·1} = {4,1,1,1} | ||
| {1·2,5·1} = {2,1,1,1,1,1} | {1·4,1·2,1·1} = {4,2,1} | ||
| {2·2,3·1} = {2,2,1,1,1} | {1·4,1·3} = {4,3} | ||
| {3·2,1·1} = {2,2,2,1} | {1·5,2·1} = {5,1,1} | ||
| {1·3,4·1} = {3,1,1,1,1} | {1·5,1·2} = {5,2} | ||
| {1·3,1·2,2·1} = {3,2,1,1} | {1·6,1·1} = {6,1} | ||
| {1·3,2·2} = {3,2,2} | {1·7} = {7} | ||
| {2·3,1·1} = {3,3,1} |
Данные разбиения представлены в порядке, где каждое разбиение удовлетворяет условию р 1> р 2>...> рl. Такой порядок называют словарным. Наиболее эффективно порождать разбиения именно в таком порядке. Для этого, начав с { n ·1}, будем переходить от одного разбиения к следующему, рассматривая самый правый элемент разбиения, ml · pl. Если ml × pl достаточно велико (ml >1), можно исключить два pl для того, чтобы добавить еще одно pl +1 (или включить еще одно pl +1, если в текущий момент его нет). Если ml =1, то ml -1× pl -1+ ml × pl достаточно велико для того, чтобы добавить pl -1+1. В любом случае то, что остается, превращается в соответствующее число единиц и формируется новое разбиение. Эту процедуру реализует алгоритм 9.
 |
Дата публикования: 2015-01-04; Прочитано: 355 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
