2015-04-01
689
Как было сказано выше, разбиение можно интерпретировать как мультимножество { m 1· p 1, m 2· p 2,…, ml · pl,}. Например для n =7 все возможные разбиения представлены в табл.2.3.
Таблица 2.3
Разбиения числа 7
| № | Разбиение | № | Разбиение |
| {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. В любом случае то, что остается, превращается в соответствующее число единиц и формируется новое разбиение. Эту процедуру реализует алгоритм представленный на рис.2.12.
|
|
|
 |
