Разбиение последовательности на несколько отрезков, схожей длины

Question

[Анатолий Гусев]

Добрый вечер.
Проблема следующая:
php скрипт берёт из БД 15 произвольных картинок, а после этого необходимо их разделить на 3 части по 5 штук в каждой, чтобы сумма высот картинок как можно меньше отличалась. Высоты известны и берутся из БД со всеми остальными данными.
Может кто-то поделиться реализацией похожего(на любом язые), либо хотя бы сказать в сторону какого алгоритма смотреть?

Answer 1

[Sekira]

$q = mysql_query("запрос");
$images = array();
while($data = mysql_fetch_array($q))
{
	$images[$data['id']] = $data['height'];
}


$variants = array();

for($i=0; $i<10; $i++)
{
	$shuffle = shuffle($images);

	$a1 = array_sum(array_slice($shuffle, 0, 5));
	$a2 = array_sum(array_slice($shuffle, 5, 5));
	$a3 = array_sum(array_slice($shuffle, -5));

	$variants[max($a1, $a2, $a3)-min($a1, $a2, $a3)] = $shuffle;
}


ksort($variants);

$best_array = array_shift($variants);

$a1 = array_slice($best_array, 0, 5); // тут будет массив для 1 столбца
$a2 = array_slice($best_array, 5, 5); // тут будет массив для 2 столбца
$a3 = array_slice($best_array, -5); // тут будет массив для 3 столбца

Меняя 10 в цикле for можно менять точность разброса высот, тем больше число, тем точнее, но больше времени потребуется.
Вариант экспериментальный, ну а вдруг подойдет. Отпишитесь пожалуйста, как попробуете данный вариант, очень интересно, что из этого выйдет.

Comments

[Анатолий Гусев]

Спасибо, опробую ваш вариант веером.
Вариант предложенный maximkou не подходит, так как разброс по высоте всёже существенный.

[Анатолий Гусев]

В вашем коде всё прекрасно, лишь один нюанс:
for($i=0; $i<10; $i++)
{
$shuffle = shuffle($images);

$a1 = array_sum(array_slice($shuffle, 0, 5));
$a2 = array_sum(array_slice($shuffle, 5, 5));
$a3 = array_sum(array_slice($shuffle, -5));

$variants[max($a1, $a2, $a3)-min($a1, $a2, $a3)] = $shuffle;
}

Здесь ругается на строку $shuffle = shuffle($images);, поэтому её следует заменить на shuffle($images); и переменную $shuffle на $images всюду.
Это для тех, кто будет использовать данный код. Плюс оптимальной выборки я добился при $i = 30

Answer 2

[TERMIK]

Это, я думаю могло бы помочь.

Answer 3

[Максим Ходырев]

$query = mysql_query("select * from images where id order by height desc limit 15");
$images = mysql_fetch_array($query);
$count = 14;
$img1 = array(); // массив 1
$img2 = array(); // массив 2
$img3 = array(); // массив 3
for ($i=0; $<5; $i++)
{
$img1[] = $images[$i];
$img1[] = $images[$count-$i-1];
$img2[] = $images[$i+1];
$img2[] = $images[$count-$i-1];
$img3[] = $images[$i+2];
$img3[] = $images[$count-$i-1];
}



может так?

Comments

[Анатолий Гусев]

С утра попробую, возможно подойдёт.

[Максим Ходырев]

т.е. сначала отсортировать по возрастанию/убыванию, потом брать первый и последний элемент, записать в первый массив, убирать (в моем случае просто передвигать указатель) эти элементы, и так по циклу

[Максим Ходырев]

но такой вариант только для вашего случая, для большого количества массивов нерационален, причем очень нерационален.

[Sekira]

В таком варианте, если например 15-ая картинка 200 пикселей, а с 1-ой по 14-ую, 50-100 пикселей, то первый столбец будет больше всех, хотя можно было взять 15-ую картинку и 4-ре картинки самых маленьких.

Answer 4

[Sekira]

Если у картинок небольшой разброс в высоте, то проще всего так:
Отсортировать 15 картинок по высоте и в 1 столбец взять 1, 6, 7, 12 и 13 картинки, во 2 столбец 2, 5, 8, 11 и 14, а в 3 столбец — 3, 4, 9,10 и 15
При этом рядом находящиеся картинки в столбцах будут примерно равны и постепенно увеличиваться к низу.

Answer 5

[Silentium]

$q = mysql_query("select * from images where id order by height desc limit 15");
$images = array(array(),array(),array());
$lengths = array(0,0,0);
while($data = mysql_fetch_array($q)) {
$n = array_search($lengths,min($lengths));
$lengths[$n] += $data['height'];
$images[$n][] = $data['id'];
}
foreach ($images as &$line) {
shuffle($line);
}

Получится, правда, не обязательно по 5, но поставить ограничение не составит труда.