Привет, Хабр! Вдруг снова захотелось написать сюда! Так как было время на выходных, я снова решил поиграться с алгоритмизацией и написал вот эту статейку. Хотел даже отправить в какой-нибудь рецензируемый журнал, но оценить тривиальность/нетривиальность данного материала я не в состоянии, так как программирование всего лишь мое хобби и то эпизодическое, поэтому, как обычно, заранее прошу прощения, если все окажется слишком простым и до боли знакомым.
Спасибо администрации Хабра за отзывчивость и молниеносную оперативность при восстановлении аккаунта!
Итак, плоды усилий долгих...
Нерекурсивный алгоритм генерации всех разбиений целого числа в лексикографическом
порядке, когда все элементы выстроены в порядке убывания, является альтернативным; в
Интернете представлено несколько способов порождения данных комбинаторных
объектов, однако, как это справедливо и относительно других комбинаторных алгоритмов,
реализации сводятся к двум типам — нерекурсивному и рекурсивному. Чаще можно встретить
реализации, которые не учитывают порядок вывода объектов или осуществляют
вывод по принципу дробления числа.
Приведенная ниже реализация работает по обратному принципу: исходное число изначально разбито на единицы, алгоритм работает до тех пор, пока число в нулевом индексе массива не станет равным сумме исходного числа. Особенностью данного алгоритма является то, что он крайне прост для понимания, однако это не лишает его некоторый специфики:
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
$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;
?>
<?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);
}
?>
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
К сожалению, не доступен сервер mySQL