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

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

Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!

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

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

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

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

Код алгоритма на PHP
<?php
$a = array(
	1,
	1,
	1,
	1,
	1,
	1,
	1,
	1,
	1
);
print_r($a);
print '<br />';
$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 '<br />';
	unset ($all,$sum,$min,$min2);
	$h++;
	}

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


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
set_time_limit(0);
//Функция генерации всех перестановок для разбиения
function perm($b) {
$b=array_reverse($b);
$a=array_reverse($b);
       while (1) {
	   	   	print_r($a);
			print '<br/>';
		   if ($a ==$b) break;
   $i=1;
	while($a[$i] >= $a[$i-1]) {
    $i++;
}
   $j=0;
	  while($a[$j] <= $a[$i]) {	
    $j++;	
}
	  $c=$a[$j];
	  $a[$j]=$a[$i];
	  $a[$i]=$c;
$c=$a;
	 $z=0;
	for ($i-=1; $i > -1; $i--) $a[$z++]=$c[$i];	
}
}

//Генерация всех композиций. Эта часть генерирует разбиения
//Заполнение массива
$g=0;
while ($g != 4){
$a[]=1;
$g++;
}

print_r($a);
print '<br>';
$w = count($a);
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;
	array_splice($a, $min2 + 1);
	$sum=array_sum($a);
	for ($j=0; $j != $w-$sum; $j++) $a[] = 1;
	perm ($a);
	unset ($sum,$min,$min2);
}

?>

При чтении описания данного алгоритма получается ли у Вас вывести его на листке бумаги?

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 32
  • 0

    3,2,2,1 -> 3,2,3. Или я не понял описание алгоритма?
    В любом случае, к любому неочевидному алгоритму следует писать доказательство.

    • 0
      Отлично, дополню алгоритм одним словом: первый минимальный (если двигаться слева направо). Внимание: последний не учитывается.
      3 2 2 1, получаем за один проход 3 3 1 1
      • 0

        Вроде так лучше.
        Дальше следовало бы расписать формальное доказательство корректности алгоритма.
        А потом можно оценить его эффективность (хотя бы на минимальном уровне в виде O(N)) и прикинуть, нет ли явных проблем (ну, запись на php с его структурами данных, заточенными под совсем другие задачи, опустим). К примеру, поиск "места для вставки единицы" полным перебором массива выглядит избыточным (можно сразу держать ссылки на "ступеньки" в массиве длиной N), но, возможно, для чисел, для которых перебор разбиений делается на компе, это и несущественно.
        На публикацию в реферируемом журнале imho слабовато (да и тема, как я понимаю, изучена ещё Эйлером), а курсовик бы вышел основательный.

        • 0
          Спасибо за отзыв, в общем-то я так сначала и подумал, что для журнала не потянет. С доказательством сложнее, но попробую, правда, на словах, без формул.
          • 0
            И, как говорят математики, то что алгоритм удовлетворяет всем условиям — «это легко видеть»: )
          • 0
            Нет, с настоящим доказательством, скорее всего ничего не выйдет. Только попытка:

            Попытка № 1 доказательства корректности алгоритма
            *разряд тут следует трактовать как индекс массива
            Леммы
            1) Каждое последующее разбиение уникально по составу, т.е. отличается хотя бы в одном разряде.
            2) Каждое последующее разбиение хранит сумму заданного числа.
            3) Члены каждого последующего разбиения выстроены по убыванию или равны между собой.
            4) Работа алгоритма заканчивается тогда, когда первый разряд равен сумме числа.

            Если в результате работы алгоритма выполнены условия 1,2,3,4 и при этом количество всех разбиений удовлетворяет (по всей видимости ) формуле Эйлера (вероятно той самой из статьи в Вики), то все разбиения найдены.

            Знаю, провалился, но попытаться должен был: )
      • 0
        3 1 1, так как + действие — разложение всего, что после 3 (наш х)
        • 0
          Два комментария:

          1. Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
            • Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
            • Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).

          2. Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).

            Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).

            «Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)


          • 0
            Поправки к №2 (конец дня, напутал лево / право в паре мест):

            … Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево слева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…

            Далее, кубики из руки выставляем слева справа от этой укороченной башенки…

            • 0
              Да, спасибо, добавил. Про движение справа налево — может быть, спорить не буду. В принципе это уже можно рассматривать как оптимизацию алгоритма или как другой алгоритм.
              Диаграмма Юнга, кстати, она как раз из кубиков, удобно действительно.

              Мне сначала пришла такая ассоциация из жизни: несколько бочек (индекс) в ряд, в каждом по ведру (значение) воды.
              • 0
                Да-да, и мне физическая модель в голове помогает иногда понять математическую задачу, хотя я учился на математика (а стал программистом). С башнями из кубиков — я хотел обеспечить как можно более медленное опускание центра тяжести конструкции из самого высокого положения (для одной башенки из N кубиков) в самое низкое (для N башенок из одного кубика).
            • 0
              Кстати, хотел бы еще дополнить: вынос первого элемента из циклов при данном подходе имеет силу как для генерации разбиений, так и для генерации сочетаний, перестановок.
              Т.е. в принципе данный подход (хоть и несколько избыточный при реализациях) вполне обобщается для других комбинаторных объектов.
              • 0
                А что будет после шага 3,1,1?
                Вначале 3,2, а затем: нет больше единиц, как отработает алгоритм?
                • 0
                  4,1 очевидно.
                  Находим наименьшее непоследнее число, — это 3, т.к. оно единственное непоследнее. Прибавляем к нему 1, а из последнего — вычитаем 1.
                • НЛО прилетело и опубликовало эту надпись здесь
                  • 0
                    Вы считаете, что есть кто-то кто должен диктовать людям, о чем им думать, когда они идут по улице?
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • 0
                        Кстати, реально почему Вы задумались об этой задаче? Какую задачу решали с помощью разбиений?
                        • 0
                          Никакую. Меня интересовали некоторое время проблемы научного творчества, а именно психология научного творчества. А тут вдруг комбинаторика подвернулась и очень кстати пришлась к некоторым моим философским (хотя, скорее, психологическим) соображениям.: )
                          В целом меня интересуют связи гуманитарных и не очень гуманитарных наук.
                          • 0
                            Ну и мой такой обобщающий вывод: особенно нет разницы во что играть: в шахматы ли, в комбинаторику, в построения каких-то абстракций. Эффект психологический при достижении результата примерно один и тот же.
                            Тут, конечно, можно спорить о сложности задач и проверять как сложность решенной задачи влияет на общий эффект… но это уже другой вопрос.
                        • 0
                          Ну не ходят люди по улице и не думают как разбить число на слагаемые от нечего делать.

                          С чего Вы это взяли? От нечего делать можно и не о таком задуматься. Вот мне как-то раз почитать в метро было нечего, так я стал в уме гауссинаду преобразовывать в полярные координаты. Не получилось, но время убил.
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • 0
                              Я выше написал мотивы. Теперь, если не сложно, объясните, почему вы так беспокоитесь за чужое состояние мыслительного процесса.
                              • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Кстати в «гауссинаду преобразовывать в полярные координаты» я тоже не вижу смысла.

                                Я краем уха слышал, что в полярных координатах интеграл от неё берётся.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Интеграл между какими пределами? Ага. А неопределённый интеграл относится к т.наз. «неберущимся».
                            • 0
                              Отвечу одним предложением за автора: программистам задачи такого рода иногда задают на интервью.
                              • НЛО прилетело и опубликовало эту надпись здесь
                            • 0
                              Шаг 3 — лишний (ноль может появиться только на последнем месте и он не влияет на сумму).
                              Ну и в коде несколько лишних операций. Вот мой вариант на JavaScript, хоть он местами и тяжело читается ;)
                              function part(n) {
                                let a = new Array(n).fill(1)
                                console.log(a)
                                while(a[0] != n) {                                                      // step 0
                                  let m = a.slice(0, -1).reduce((m,n,i)=>(a[m]>n ? i:m), 0)             // step 1
                                  ++a[m]; --a[a.length-1]                                               // step 2    
                                  a = a.concat(new Array(a.splice(m+1).reduce((s,n)=>s+n, 0)).fill(1))  // step 4
                                  console.log(a)
                                }
                              }
                              
                              • 0
                                Спасибо. Интересно, но позвольте одно замечание, если бы вместо комментария написали хоть краткую заметку об оптимизации алгоритма, то пользы было бы больше… желательно с подробным объяснением.

                                Дело в том, что большинство комментаторов, включая автора, понимают, что в реализации есть лишние шаги.
                                Без попытки обидеть.
                                • 0
                                  function partI(n) {
                                    let a = new Array(n).fill(1);
                                    console.log(a)
                                    while(a.length>1) {
                                  	let sum = a.pop(), i = a.length -1;
                                  	while(i>0 && a[i-1]==a[i]){
                                  		sum += a.pop();
                                  		--i;
                                  	}
                                  	a[i]+=1;
                                  	sum-=1;
                                  	a = a.concat(new Array(sum).fill(1));
                                  	console.log(a);
                                    }
                                  }
                                  


                                  В случае JavaScript так лучше.
                                  1. Выталкиваем последний элемент массива в переменную sum;
                                  2. Выталкиваем из массива элементы один за другим и прибавляем их к sum до тех пор, пока они равны друг другу, последний из них (равных друг другу элементов) — не выталкиваем, он — искомый.
                                  3. Искомый элемент увеличиваем на единицу, а переменную sum — уменьшаем на единицу.
                                  4. Раскладываем значение sum в массив единиц и приклеиваем его к концу исходного массива.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.