A
A
Anatoly Gusev2012-01-17 22:52:02
PHP
Anatoly Gusev, 2012-01-17 22:52:02

Splitting a sequence into several segments of similar length

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 the question

In order to leave comments, you need to log in

5 answer(s)
S
Sekira, 2012-01-18
@MximuS

$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.

T
TERMIK, 2012-01-17
@TERMIK

This I think might help.

M
Maxim Khodyrev, 2012-01-17
@maximkou

$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?

S
Sekira, 2012-01-18
@Sekira

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.

S
Silentium, 2012-01-23
@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);
}

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

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question