Привет, Хабр! Вдруг снова захотелось написать сюда! Так как было время на выходных, я снова решил поиграться с алгоритмизацией и написал вот эту статейку. Хотел даже отправить в какой-нибудь рецензируемый журнал, но оценить тривиальность/нетривиальность данного материала я не в состоянии, так как программирование всего лишь мое хобби и то эпизодическое, поэтому, как обычно, заранее прошу прощения, если все окажется слишком простым и до боли знакомым.
Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!
Итак, плоды усилий долгих...
Нерекурсивный алгоритм генерации всех разбиений целого числа в лексикографическом
порядке, когда все элементы выстроены в порядке убывания, является альтернативным; в
Интернете представлено несколько способов порождения данных комбинаторных
объектов, однако, как это справедливо и относительно других комбинаторных алгоритмов,
реализации сводятся к двум типам — нерекурсивному и рекурсивному. Чаще можно встретить
реализации, которые не учитывают порядок вывода объектов или осуществляют
вывод по принципу дробления числа.
Приведенная ниже реализация работает по обратному принципу: исходное число изначально разбито на единицы, алгоритм работает до тех пор, пока число в нулевом индексе массива не станет равным сумме исходного числа. Особенностью данного алгоритма является то, что он крайне прост для понимания, однако это не лишает его некоторый специфики:
1) Первый объект просто выводится на экран в самом начале, таким образом, он вынесен за пределы циклов, фактически является инициализирующим;
2) Существует несколько способов реализации переноса единицы, которые могут, как упростить код, так и сделать его более запутанным;
3) Данная нерекурсивная реализация может служить наглядным примером для объяснения генерации комбинаторных объектов на нескольких процессорах, после незначительной модификации. Для разделения генерации на процессоры достаточно: а) определить элемент по его номеру и сделать инициализирующим; б) определить момент для остановки работы. Например, если известно число объектов, генерируемых на одном процессоре, то достаточно ввести еще одну инкрементируемую переменную в верхний цикл и изменить условие выхода из самого верхнего цикла по достижении требуемого количества.
Код на языке PHP приведен только для демонстрации корректности алгоритма и может содержать лишние языковые средства, которые добавляют реализации избыточности.
Описание алгоритма
Дано: исходный массив в виде единиц — А (1,1,1,1,1).
Шаги
0) Если получили сумму (в случае реализации ниже, если нулевой индекс равен сумме числа), тогда остановка алгоритма.
1) Двигаясь по массиву слева направо, искать в массиве А первый минимальный элемент — x,
последний элемент не учитывается (не участвует в поиске минимального).
2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).
3) Если в массиве А есть ноль — 0, то удалить последний элемент.
4) Разложить сумму всех элементов после измененного элемента — x – на единицы.
Пример
А=(1,1,1,1,1)
2,1,1,1
2,2,1
3,1,1
Update:
Операция с поиском и удалением 0 в массиве лишняя (так как используется array_splice, а затем новое заполнение массива), как правильно было замечено в комментарии участником dev26
Выводы
Хотел бы в конце поделиться одним наблюдением, я очень долго пытался понять, почему одни алгоритмы понятны сразу и легки для кодирования, а другие заставляют мучиться… и мучиться порой долго. Должен отметить, что этот алгоритм у меня получилось закодировать почти сразу, но только после того, как я получил однозначно понятное описание каждого шага. И тут есть важный момент, понять алгоритм и описать — задачи одна другой не легче. Однако, в алгоритмизации и составлении описания, особенно важным оказывается то, какими глаголами описываются действия в алгоритме — это (субъективно) в конечном счете может влиять и на конечную реализацию.
Литература
[1] Donald E. Knuth. The Art of Programming. Vol. 4. 2008.
[2] Dennis Ritchie and Brian Kernighan. The C Programming Language. 1978.
[3] Aleksandr Shen. Algorithms and Programming: Problems and Solutions.
[4] ru.wikipedia.org/wiki/Разбиение_числа
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
P.S. Несмотря на приведенный список литературы, алгоритм пришлось выводить заново.
Еще одно дополнение:
Вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок. В принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для генерации других комбинаторных объектов.
UPDATE
Алгоритм разбиений в соединении с алгоритмом перестановок позволяет генерировать и все композиции числа. Идея простая: для каждого разбиения вызывается функция генерации всех перестановок для этого разбиения.
Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!
Итак, плоды усилий долгих...
Нерекурсивный алгоритм генерации всех разбиений целого числа в лексикографическом
порядке, когда все элементы выстроены в порядке убывания, является альтернативным; в
Интернете представлено несколько способов порождения данных комбинаторных
объектов, однако, как это справедливо и относительно других комбинаторных алгоритмов,
реализации сводятся к двум типам — нерекурсивному и рекурсивному. Чаще можно встретить
реализации, которые не учитывают порядок вывода объектов или осуществляют
вывод по принципу дробления числа.
Приведенная ниже реализация работает по обратному принципу: исходное число изначально разбито на единицы, алгоритм работает до тех пор, пока число в нулевом индексе массива не станет равным сумме исходного числа. Особенностью данного алгоритма является то, что он крайне прост для понимания, однако это не лишает его некоторый специфики:
1) Первый объект просто выводится на экран в самом начале, таким образом, он вынесен за пределы циклов, фактически является инициализирующим;
2) Существует несколько способов реализации переноса единицы, которые могут, как упростить код, так и сделать его более запутанным;
3) Данная нерекурсивная реализация может служить наглядным примером для объяснения генерации комбинаторных объектов на нескольких процессорах, после незначительной модификации. Для разделения генерации на процессоры достаточно: а) определить элемент по его номеру и сделать инициализирующим; б) определить момент для остановки работы. Например, если известно число объектов, генерируемых на одном процессоре, то достаточно ввести еще одну инкрементируемую переменную в верхний цикл и изменить условие выхода из самого верхнего цикла по достижении требуемого количества.
Код на языке PHP приведен только для демонстрации корректности алгоритма и может содержать лишние языковые средства, которые добавляют реализации избыточности.
Описание алгоритма
Дано: исходный массив в виде единиц — А (1,1,1,1,1).
Шаги
0) Если получили сумму (в случае реализации ниже, если нулевой индекс равен сумме числа), тогда остановка алгоритма.
1) Двигаясь по массиву слева направо, искать в массиве А первый минимальный элемент — x,
последний элемент не учитывается (не участвует в поиске минимального).
2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).
4) Разложить сумму всех элементов после измененного элемента — x – на единицы.
Пример
А=(1,1,1,1,1)
2,1,1,1
2,2,1
3,1,1
Код алгоритма на PHP
<?php /*Генерация всех разбиений. Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1, 1, 1 ); $n = count($a); while (1) { /*Печать и выход. Print end exit.*/ print_r($a); if ($a[0] == $n) break; /*Элемент в нулевом индексе нашего динамического массива на текущий момент. First element of our dynamic array*/ $first_elem = $a[0]; /*Размер массива на текущий момент. Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /*Найдем элемент меньше первого. Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /*Перенос элемента "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /*Обрежем массив и найдем сумму его элементов. We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /*Добавим в массив единицы заново с учетом суммы. Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /*Обнулим переменную. Unset min_elem.*/ unset($min_elem); } ?>
Update:
Операция с поиском и удалением 0 в массиве лишняя (так как используется array_splice, а затем новое заполнение массива), как правильно было замечено в комментарии участником dev26
Выводы
Хотел бы в конце поделиться одним наблюдением, я очень долго пытался понять, почему одни алгоритмы понятны сразу и легки для кодирования, а другие заставляют мучиться… и мучиться порой долго. Должен отметить, что этот алгоритм у меня получилось закодировать почти сразу, но только после того, как я получил однозначно понятное описание каждого шага. И тут есть важный момент, понять алгоритм и описать — задачи одна другой не легче. Однако, в алгоритмизации и составлении описания, особенно важным оказывается то, какими глаголами описываются действия в алгоритме — это (субъективно) в конечном счете может влиять и на конечную реализацию.
Литература
[1] Donald E. Knuth. The Art of Programming. Vol. 4. 2008.
[2] Dennis Ritchie and Brian Kernighan. The C Programming Language. 1978.
[3] Aleksandr Shen. Algorithms and Programming: Problems and Solutions.
[4] ru.wikipedia.org/wiki/Разбиение_числа
[5] en.wikipedia.org/wiki/De_Arte_Combinatoria
P.S. Несмотря на приведенный список литературы, алгоритм пришлось выводить заново.
Еще одно дополнение:
Вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок. В принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для генерации других комбинаторных объектов.
UPDATE
Алгоритм разбиений в соединении с алгоритмом перестановок позволяет генерировать и все композиции числа. Идея простая: для каждого разбиения вызывается функция генерации всех перестановок для этого разбиения.
Генерация композиций. PHP
<?php /*Генерация всех разбиений. Generate all partitions.*/ $a = array( 1, 1, 1, 1, 1 ); $n = count($a); $h=0; while (1) { /*Печать всех перестановок и условие выхода. Permutations and exit.*/ permute($a, $h); if ($a[0] == $n) break; /*Элемент в нулевом индексе нашего динамического массива на текущий момент. First element of our dynamic array*/ $first_elem = $a[0]; /*Размер массива на текущий момент. Length of an array*/ $c = count($a) - 1; $i = 0; while ($i != count($a) - 1) { /*Найдем элемент меньше первого. Here we search min. element.*/ if ($a[$i] < $first_elem) { $first_elem = $a[$i]; $min_elem = $i; } $i++; } if (empty($min_elem)) $min_elem = 0; /*Перенос элемента "1". Here we transfer "1". */ $a[$min_elem]+= 1; $a[$c]-= 1; /*Обрежем массив и найдем сумму его элементов. We cut the array * and count the sum of elements.*/ array_splice($a, $min_elem + 1); $array_sum = array_sum($a); /*Добавим в массив единицы заново с учетом суммы. Here we add 1 (fill) to the array ( taking into account the sum ).*/ for ($j = 0; $j != $n - $array_sum; $j++) $a[] = 1; /*Обнулим переменную. Unset min_elem.*/ unset($min_elem); } /*Функция перестановок. Permutations function.*/ function permute($b,&$h) { /*Дублируем массив и перевернем его. Это нужно для выхода * из алгоритма. * Here we make a copy and reverse our array. It is necessary to * stop the algorithm.*/ $a = $b; $b = array_reverse($b); while (1) { /*Печать и условие выхода. Here we print and exit.*/ print_r($a); print "\n"; if ($a == $b) break; /*Ищем слдующую перестановку. * Here we search next permutation.*/ $i = 1; while ($a[$i] >= $a[$i - 1]) { $i++; } $j = 0; while ($a[$j] <= $a[$i]) { $j++; } /*Обмен. Here we change.*/ $c = $a[$j]; $a[$j] = $a[$i]; $a[$i] = $c; /*Обернем хвост. Tail reverse.*/ $c = $a; $z = 0; for ($i-= 1; $i > - 1; $i--) $a[$z++] = $c[$i]; } } ?>
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
При чтении описания данного алгоритма получается ли у Вас вывести его на листке бумаги?
48.72%Да, сразу19
41.03%Совсем непонятно16
23.08%Затрудняюсь с ответом9
Проголосовали 39 пользователей. Воздержались 26 пользователей.
