[recovery mode] Нерекурсивный алгоритм генерации всех разбиений целого числа

Привет, Хабр! Вдруг снова захотелось написать сюда! Так как было время на выходных, я снова решил поиграться с алгоритмизацией и написал вот эту статейку. Хотел даже отправить в какой-нибудь рецензируемый журнал, но оценить тривиальность/нетривиальность данного материала я не в состоянии, так как программирование всего лишь мое хобби и то эпизодическое, поэтому, как обычно, заранее прошу прощения, если все окажется слишком простым и до боли знакомым.
Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!

Итак, плоды усилий долгих...

Нерекурсивный алгоритм генерации всех разбиений целого числа в лексикографическом
порядке, когда все элементы выстроены в порядке убывания, является альтернативным; в
Интернете представлено несколько способов порождения данных комбинаторных
объектов, однако, как это справедливо и относительно других комбинаторных алгоритмов,
реализации сводятся к двум типам — нерекурсивному и рекурсивному. Чаще можно встретить
реализации, которые не учитывают порядок вывода объектов или осуществляют
вывод по принципу дробления числа.

Приведенная ниже реализация работает по обратному
принципу: исходное число изначально разбито на единицы, алгоритм работает до тех пор,
пока число в нулевом индексе массива не станет равным сумме исходного числа.
Особенностью данного алгоритма является то, что он крайне прост для понимания, однако
это не лишает его некоторый специфики:

1) первый объект просто выводится на экран в
самом начале, таким образом, он вынесен за пределы циклов, фактически является
инициализирующим;
2) существует несколько способов реализации переноса единицы,
которые могут, как упростить код, так и сделать его более запутанным;
3) данная нерекурсивная реализация может служить наглядным примером для объяснения генерации комбинаторных объектов на нескольких процессорах, после незначительной модификации. Код на языке PHP приведен только для демонстрации корректности алгоритма и может содержать лишние языковые средства, которые добавляют реализации избыточности.

Описание алгоритма
Дано: исходный массив в виде единиц — А (1,1,1,1).
Шаги
1) Двигаясь по массиву слева направо, искать в массиве А минимальный элемент — x,
последний элемент не учитывается.
2) Перенести единицу из конца (последнего элемента) в найденный минимальный элемент x
(равносильно увеличению x на единицу и уменьшению на единицу последнего элемента).
3) Если в массиве А есть ноль — 0, то удалить последний элемент.
4) Разложить сумму всех элементов после измененного элемента — x – на единицы.
Пример
А=(1,1,1,1,1)
2,1,1,1
2,2,1
3,1,1

Код алгоритма на PHP

';
$w = count($a);
$h = 0;

while ($a[0] != $w)
        {
        $min = $a[0];
        $c = count($a) - 1;
        $i = 0;
        while ($i != count($a) - 1)
                {
                if ($a[$i] < $min)
                        {
                        $min = $a[$i];
                        $min2 = $i;
                        }

                $i++;
                }

        if ($min2 == 0) $min2 = 0;
        $a[$min2]+= 1;
        $a[$c]-= 1;
        if (in_array(0, $a)) array_pop($a);
        array_splice($a, $min2 + 1);
        foreach($a as $v)
                {
                $sum+= $v;
                }

        $j = 0;
        $all = $w - $sum;
        while ($j != $all)
                {
                $a[] = 1;
                $j++;
                }

        print_r($a);
        print '
';
        unset($all);
        unset($sum);
        unset($min);
        unset($min2);
        $h++;
        }

echo 'Amount: ' . ++$h;
?>

Выводы
Хотел бы в конце поделиться одним наблюдением, я очень долго пытался понять, почему одни алгоритмы понятны сразу и легки для кодирования, а другие заставляют мучиться… и мучиться порой долго. Должен отметить, что этот алгоритм у меня получилось закодировать почти сразу, но только после того, как я получил однозначно понятное описание каждого шага. И тут есть важный момент, понять алгоритм и описать — задачи одна другой не легче. Однако, в алгоритмизации и составлении описания, особенно важным оказывается то, какими глаголами описываются действия в алгоритме — это (субъективно) в конечном счете может влиять и на конечную реализацию.

Литература
[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] http://ift.tt/2rc6MaY
[5] http://ift.tt/2rFIxTU

P.S. Несмотря на приведенный список литературы, алгоритм пришлось выводить заново.

Let's block ads! (Why?)