extreme data sortin' & devidin'

[appel]

I'm working on a link-management script, with a cool sorting feature... The idea is that it counts the total amount of links and then devides them equally over a pre-defined set of coloms, whilst remaining listed under its parent categorie.

Some examples:
In case of 34 links and 3 cols: 12-11-11
In case of 65 links and 4 cols: 17-16-16-16
In case of 109 links and 2 cols: 55-54

Notice how the first number is rounded up (like with php's ceil function).

I'm afraid it doesn't stop there... Every link is categorized and should remain listed under its parent category without breaking up. So if we had the following situation:

cat 1 (containing 9 links)
cat 2 (containing 5 links)
cat 3 (containing 2 links)
cat 4 (containing 8 links)
cat 5 (containing 4 links)

the outcome should be a table that's something like:

+--------------+
|[b]CAT4[/b]|[b]CAT2[/b]|[b]CAT1[/b]|
|Lnk1|Lnk1|Lnk1|
|Lnk2|Lnk2|Lnk2|
|Lnk3|Lnk3|Lnk3|
|Lnk4|Lnk4|Lnk4|
|Lnk5|Lnk5|Lnk5|
|Lnk6|    |Lnk6|
|Lnk7|[b]CAT5[/b]|Lnk7|
|Lnk8|Lnk1|Lnk8|
|    |Lnk2|Lnk9|
|[b]CAT3[/b]|Lnk3|    |
|Lnk1|Lnk4|    |
|Lnk2|    |    |
+--------------+

Let me explain that; First of all php should do some math (28/3) to be able to come up with 3 ($cols) almost equal numbers: 10, 9, 9. Then, it should take a look at the hierarchy of the links and then, based on those 3 numbers, calculate how to devide the cats in such a way they are devided as equally as possible.

r u still with me..? 😃

Got something going here: http://links.nr78.net : but the three coloms should've been as equally devided as possible.

So far i came up with this (stripped out some parts for the sake of clarity):

<?php 

$cols = 3; 


$result = mysql_query("SELECT * FROM $tbl[cat] ORDER BY 'name' ASC"); 
while ($row = mysql_fetch_array($result)) { 
$catid = $row["id"]; 
$naam = $row["naam"]; 
$links .= '<p><span class="header">'.$naam.'</span><br />'."\n"; 

    $sql = "SELECT * FROM $tbl[links] WHERE catid = '$catid'"; 
    $res = mysql_query($sql) or die (mysql_error()); 

    // links 
    while ($list = mysql_fetch_object($res)) { 
    $links .= '&middot; <a>'.$list->naam.'</a><br />'."\n"; 
    } 
} 


// calculate table 
echo '<table cellpadding="5" cellspacing="1"><tr>'; 
for($i=1;$i<=$cols;$i++) { 
echo '<td bgcolor="#eeeeee" nowrap>'.$links[$i].'</td>'; 
} 
echo '</tr></table>'; 

?>

As you can probably see it doesn't even come close to what i described above 🙁

Geez, hope i'm made myself clear and i hope someone is able to help me, 'cause i ain't got much hair left...

Thanks in advance!

appel

[the_Igel]

Here's the algorythm (realisation is left as an exercise 🙂)

suppose $cat = array($cat_name => $cat_count) ordered by value.

Suppose $column[][] is 2D array listing cat_names in columns.
At the start $column is empty.

for $i = 0 to N - 1 where N is number of columns we take the biggest element from $cat and put it the $column[$i][].

Now we got N columns each with one category in it.

Then for all the rest of categories we search for the shortest column at the moment (i.e. the sum of all the cat_count for categories in this column is minimal) and put the current category in there.

[appel]

wow...

Thanks a lot for your swift answer Igel, appreciate it! Even though your reply is written clearly, i still don't totally grasp what you're saying yet. :o

Would you mind going a little deeper on this subject..?

for example: what exactly should i fill in $column[][]?
something like this?
$column[catid=1][col=3]
$column[catid=2][col=2]
$column[catid=3][col=3]
and how would i get $cat[] sorted so that they're devided equally?

my current $cat array:

Array
(
    [Code & Design] => 9
    [Inspiration] => 7
    [News] => 3
    [Weblogs] => 7
    [Bizz] => 3
    [Information] => 2
    [Projects] => 2
)

thanks again for your time!

ap

[the_Igel]

Send me $5 and I tell you how to become a millionaire 🙂

OK. Here it is.

Lets assume

define('N', 4); // number of columns

$data = array(
'categ1' => 5,
'categ2' => 15,
'categ3' => 23,
'categ4' => 4,
'categ5' => 8,
'categ6' => 12,
'categ7' => 19);

rsort($data); // The biggest on top

$columns = array();
$i = 0;
foreach ($data as $cat => $lines)
{
if ($i = N) break;
$data[$i][$cat] = $lines;
unset($data[$cat]);   // Hope it works, but not sure
$i++;
}

$count = count($data);

foreach($data as $cat => $lines)
{
$add_to = search_shortest_column_in_columns_array(); //write it yourself
// It's about summing values by rows of $columns and finding smallest value
$data[$add_to][$cat] => $lines;
}


// now print your columns using keys from $data rows as handles to categories

Is this clear enough? Or more details needed? 🙂

[the_Igel]

And yes, it's not optimal algorithm, for example in case you have categories 10, 9, 8, 8 & 7 links long for two columns, it will make 10 + 8 and 9 + 8 + 7 columns, not 10 + 9 and 8 + 8 + 7.
But it's rather simple, and for a moment I can't invent better one of reasonable complexity.

[appel]

Once again, thanks for taking the time to help me! I tried the suggestion in your post, but unluckily it threw a few of errors.

(copypasting turns [space] into a weird character!)

i tried to correct them, taking it one line a step, but i got stuck half way down 🙁

this is how it is now (with comments):

<?php

/* contains $cols (3) */
require_once("common.php");

define('N', $cols);

/* takes the cats from the db, counts links per cat and puts it in $data */
$result = mysql_query("SELECT * FROM $tbl[cat] ORDER BY 'name' ASC") or die (mysql_error());
$totalcat = mysql_num_rows($result) or die (mysql_error());
	while ($row = mysql_fetch_array($result)) {
		$catid = $row["id"];
		$naam = $row["naam"];
		$sql = "SELECT * FROM $tbl[links] WHERE catid = '$catid' ORDER BY naam ASC";
		$result3 = mysql_query($sql) or die (mysql_error());
		$totallink = mysql_num_rows($result3) or die (mysql_error());
		$data[$naam] = $totallink;
		}

rsort($data);

/* how should i fill this array..? */
$columns = array();

$i = 0;

foreach($data as $cat => $lines) {

	/* added xtra = */
	if($i==N) break;

	/* threw an error: Warning: Cannot use a scalar value as an array
	somehow $data isn't considered an array */
	$data[$i][$cat] = $lines;

	unset($data[$cat]); // Hope it works, but not sure (it did!)
}

/* echoes '7' */
$count = count($data);

foreach($data as $cat => $lines) {
/* will write that as soon as i understand $columns :D */
// $add_to = search_shortest_column_in_columns_array(); //write it yourself
// It's about summing values by rows of $columns and finding smallest value
// $data[$add_to][$cat] = $lines;
}

// now print your columns using keys from $data rows as handles to categories

?>

Ps. don't mind it's not optimal, i'd be glad if i got this one working!

<?php
$5 = "gratitude & respect";
mail($igel, $subject, $5);
?>

[the_Igel]

Oops. Sorry.

foreach ($data as $cat => $lines)
{
if ($i = N) break;
$data[$i][$cat] = $lines;
unset($data[$cat]);
$i++;
}

must be

foreach ($data as $cat => $lines)
{
if ($i = N) break;
$columns[$i][$cat] = $lines;
unset($data[$cat]);
$i++;
}

Maybe there's something else, but this point is big enough 🙂

[the_Igel]

I'm trying to put it to work, do not bother correcting it. I've already found loads of bugs. Give me half an hour.

[appel]

[edit]didn't saw your last post after i posted this one... thanks for helping me out![/edit]

Thanks again for you patience!

No errors, but no output either 😕

<?php

/* contains $cols (3) */
require_once("common.php");

define('N', $cols);

/* takes the cats from the db, counts links per cat and puts it in $data */
$result = mysql_query("SELECT * FROM $tbl[cat] ORDER BY 'name' ASC") or die (mysql_error());
$totalcat = mysql_num_rows($result) or die (mysql_error());
	while ($row = mysql_fetch_array($result)) {
		$catid = $row["id"];
		$naam = $row["naam"];
		$sql = "SELECT * FROM $tbl[links] WHERE catid = '$catid' ORDER BY naam ASC";
		$result3 = mysql_query($sql) or die (mysql_error());
		$totallink = mysql_num_rows($result3) or die (mysql_error());
		$data[$naam] = $totallink;
		}

So far so good...

rsort($data);

it sorts them allright, but this also somehow transforms $data's keys from stringvalues to nrs... is that a good thing?

$columns = array();

$i = 0;

foreach($data as $cat => $lines) {

	/* added xtra = */
	if($i==N) break;

	$columns[$i][$cat] = $lines;
	unset($data[$cat]); // Hope it works, but not sure (it did!)
}


$count = count($data);

no problem here mesa thinks...

foreach($data as $cat => $lines) {

/* like this? */
$add_to = min($columns[0]);

// It's about summing values by rows of $columns and finding smallest value
$data[$add_to][$cat] = $lines;
}

// now print your columns using keys from $data rows as handles to categories
foreach($data as $key) {
echo $columns[$key].'<br />';
}


?>

This is the part i don't quite get yet. I guess al these multidimensional arrays are confusing me. am i getting it right (or even close?)

if i do a print_r($data) right after the sql i get:

Array
(
    [Code & Design] => 9
    [Inspiration] => 7
    [News] => 3
    [Weblogs] => 7
    [Bizz] => 3
    [Information] => 2
    [Projects] => 2
)

[the_Igel]

Oh yeah, at last. Here it is.

error_reporting(E_ALL);
define('N', 4); // number of columns

$data = array(
'categ1' => 5,
'categ2' => 15,
'categ3' => 23,
'categ4' => 4,
'categ5' => 8,
'categ6' => 12,
'categ7' => 19);


arsort($data); // The biggest on top

$columns = array();
$i = 0;
foreach ($data as $cat => $lines)
{
if ($i == N) break;
$columns[$i][$cat] = $lines;
unset($data[$cat]);   // Hope it works, but not sure
$i++;
}

$count = count($data);

function search_shortest_column_in_columns_array()
{
global $columns;
$counts = array();
foreach ($columns as $key => $column)
	$counts[$key] = array_sum($column);
asort($counts);
reset($counts);
return key($counts);
}

foreach($data as $cat => $lines)
{
$add_to = search_shortest_column_in_columns_array(); //write it yourself
$columns[$add_to][$cat] = $lines;
}
print_r($columns);

It print_r() array, each element of which is an hash of category_name => number_of_columns pairs.

Of course, you need not to print_r() this array, but to print your columns with links, still it's up to you.

At least this script works fine. Total number of lines for a column varies from 20 to 23 with my data.

Note that here's a bunch of non-PHP3 functions, in case you use some old version.

PS All that array stuff always make my head ache 🙂

[the_Igel]

And, like you, I haven't seen your previous post before posting mine 🙂

[the_Igel]

And a remark about search_shortest_column_in_columns_array().

It may be

{
global $columns;
return array_search(min($columns), $columns);
}

And the script in the whole is a nice object for optimization, leaving alone the algorithm 🙂

[the_Igel]

Um. No, last post doesn't count. Not that clearly thinking today I am. You can't write that function like I wrote. we're not just searching for min(), it's way more complicated what we do.

[appel]

Igel, i'd kiss you if you weren't living like 1055.8 kilometres away!

It is indeed working very well, shouldn't be too hard to format it nicely now 😃

'error_reporting(E_ALL);' looks like a very nice function too. it shows some errors in my common.php.

Thanks again, i owe you bigtime,

appel

[the_Igel]

Not sure about kissing, but I'm glad to help you. Is there something more I can do for you? 🙂

[appel]

I got it working perfectly, check it out at: http://news.nr78.net/. The links on the right side were formatted using your marvelous coding 😃!

once more: thanks a lot!

Is there something more I can do for you?

Well, actually there is one more thing...

The 'error_reporting(E_ALL)' showed a whole-lotta notices. For example: Notice: Use of undefined constant cat - assumed 'cat' in d:\localhost\lab\projects\ds\links\common.php on line 8.

In this example PHP is talking 'bout a variable in common.php:
$tbl[cat] = "cat";

What do these notices mean? What's a Undefined Constant?

Ps. "As I came to your site with images off, that was hard to understand that there's something except the first page. Didn\'t you here about alt-attributes? 🙂"
you're absolutely right! I was kinda in a hurry to put something up there, so i must have forgotton to put those alt-attributes in there!

btw: What website are you running?

[jmcneese]

you really should use $tbl['cat'], it's "better".

anyway. hoe gaat het, joh?

[appel]

bijzonder goed, dank je!
Hoest met je vriendin?

[jmcneese]

vriendin? mijn vrouw, bedoel je 😉. ik ben net getrouwd, augustus 27de.

anyway, het gaat goed met haar, aleen een beetje moe. een tweeling is heel erg druk, weet je. 🙂

(apologies for my horrible grammar)

[appel]

Gefeliciteerd! Ik wens jullie allebei alle geluk!

maar nou moet je toch ff m'n geheugenzeef opfrissen:
kennen wij elkaar..? 😃