Алгоритм порождения разбиений
Как было сказано выше, разбиение можно интерпретировать как мультимножество {m1·p1,m2·p2,…,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.
 |