Splitting a sequence into several segments of similar length

Question

PHP

Good evening.
The problem is the following:
the php script takes 15 random images from the database, and after that it is necessary to divide them into 3 parts, 5 pieces each, so that the sum of the heights of the images differs as little as possible. Heights are known and are taken from the database with all other data.
Can someone share the implementation of a similar one (in any language), or at least say in the direction of which algorithm to look?

Answer 1

$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 столбца

By changing 10 in the for loop, you can change the accuracy of the height spread, the larger the number, the more accurate, but it will take more time.
An experimental option, but it might work. Please unsubscribe as you try this option, it's very interesting what will come of it.

Answer 2

This I think might help.

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];
}

maybe so?

Answer 4

If the pictures have a small spread in height, then the easiest way is:
Sort 15 pictures by height and take 1, 6, 7, 12 and 13 pictures in 1 column, 2, 5, 8, 11 and 14 in 2 column, and 3 column — 3, 4, 9,10 and 15
In this case, the adjacent pictures in the columns will be approximately equal and gradually increase towards the bottom.

Answer 5

$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);
}

It turns out, however, not necessarily 5, but it will not be difficult to set a limit.