Distributing items into columns, or evenly grouping items of varying size

This article relates to the computer programming challenge of organising items of varying size into groups. The ideas could apply to all sorts of concepts, but to keep it simple I am going to use the example of taking a HTML list and distributing it into columns using PHP for display purposes.

Consider these HTML lists:

I would like to put this output into three columns, but still keep each list together as one unit.

But first, to make things easier, and because I'm a PHP nut, let me first write a function to generate the HTML output for the list:

<?php
/**
 * Plain lists.
 */
function lists_html($lists) {
   $output = "";
   foreach ($lists as $list => $items) {
      $output .= "<div class=\"list-container\">\n";
      $output .= "  <h3>". $list ."</h3>\n";
      $output .= "  <ul>\n";
      foreach ($items as $item) {
         $output .= "    <li>";
         $output .= $item;
         $output .= "</li>\n";
      }
      $output .= "  </ul>\n";
      $output .= "</div>\n";
   }
   return $output;
}
?>

That function loops through an array of lists, where each list is an array too. Here is array for the set of lists from the above example:

$example = array(
   "Category Alpha" => array(
      "alpha item one",
      "alpha item two",
   ),
   "Category Beta" => array(
      "beta item one",
      "beta item two",
      "beta item three",
      "beta item four",
   ),
   "Category Gamma" => array(
      "gamma item one",
   ),
   "Category Delta" => array(
      "delta item one",
      "delta item two",
      "delta item three",
      "delta item four",
      "delta item five",
      "delta item six",
      "delta item seven",
      "delta item eight",

   ),
   "Category Epsilon" => array(
      "epsilon item one",
   ),
);

To output it with the function I would call it like so:

print lists_html($example);

There is also a bit of CSS that goes along with this:

.list-container {
   border:  1px solid #ccc;
   padding: 1em;
}

This is just for the style of the div container around each list. The style I've chosen isn't pretty - but it does allow you to see what is going on.

And that will give me a dynamically-generated HTML list identical to the manually typed one shown near the top of this article:

Simple enough? I'm going through this one step at a time so you can see how this will evolve.

Now in my ideal philosophy, this is all you would do in terms of outputting the markup programatically, you could then use JavaScript to arrange this output into the type of display you like. But for the purposes of this article I will modify the function I wrote to try to come up with a PHP solution.

Firstly, the obvious method to create columns you might try is to constrain each list to a certain width and float them across:

<?php
/**
 * Simple float.
 */
function columns_float_lists_html($lists, $number_of_columns) {
   $output = "";
   foreach ($lists as $list => $items) {
      $output .= "<div class=\"float-". $number_of_columns ."-columns\">\n";
      $output .= "  <div class=\"list-container\">\n";
      $output .= "    <h3>". $list ."</h3>\n";
      $output .= "    <ul>\n";
      foreach ($items as $item) {
         $output .= "      <li>";
         $output .= $item;
         $output .= "</li>\n";
      }
      $output .= "</ul>\n";
      $output .= "</div>\n";
      $output .= "</div>\n";
   }
   return $output;
}
?>

You can see there is now a parameter for the number of columns, so we can call the function like this:

print float_lists_html($example, 3);

I'm avoiding hardcoding style attributes to set the width and using a class with the number of columns. So there is some corresponding CSS:

.float-3-columns {
   float: left;
   width: 33%;
}

Of course if you're supplying a different number of columns you would include different CSS styles:

.float-1-columns {
   float: left;
   width: 100%;
}
.float-2-columns {
   float: left;
   width: 50%;
}
.float-3-columns {
   float: left;
   width: 33%;
}
.float-4-columns {
   float: left;
   width: 25%;
}
.float-5-columns {
   float: left;
   width: 20%;
}

I sure hope you're clever enough to see the pattern there, the width each time is floor(100 / $number_of_columns), but that's up to you.

Anyway, let's see what our output is for this!

Oh no! It completely buggered up near the end there. If you understand CSS you'll realise what's going on here, each floated item goes into the first spot that it can go on the next line, and with varying sized items this is the unfortunate layout you get.

A satisfactory solution is to wrap each row in a container, so that I can use CSS to clear each row onto a new line:

<?php
/**
 * Float into cleared rows.
 */
function columns_float_rows_lists_html($lists, $number_of_columns) {
   $output = "";
   $column = 0;
   $row_open = FALSE;
   foreach ($lists as $list => $items) {
      if ($column == 0) {
        $output .= "<div class=\"row-container\">\n";
        $row_open = TRUE;
      }
      $output .= "  <div class=\"float-". $number_of_columns ."-columns\">\n";
      $output .= "    <div class=\"list-container\">\n";
      $output .= "    <h3>". $list ."</h3>\n";
      $output .= "      <ul>\n";
      foreach ($items as $item) {
         $output .= "        <li>";
         $output .= $item;
         $output .= "</li>\n";
      }
      $output .= "      </ul>\n";
      $output .= "    </div>\n";
      $output .= "  </div>\n";
      if ($column == $number_of_columns - 1) {
        $output .= "</div>\n";
        $row_open = FALSE;
        $column = 0;
      }
      else {
         $column++;
      }
   }
   // Failsafe to close last row.
   if ($row_open) {
      $output .= "</div>\n";
   }
   return $output;
}
?>

This is the accompanying CSS:

.row-container {
   border:  1px solid green;
   overflow : hidden;
   _height : 1%; 
}

The green border is just to show you the rows, but the overflow and _height properties are for clearing the row, I got that CSS from this article.

Using the same $example array as before we will call the function like so:

print columns_float_rows_lists_html($example, 3);

And this is how the output will appear:

That's perfectly fine for a lot of cases. This isn't entirely what we were after though; we're outputting rows with columns in them, not columns per se, and there is a bit of space between the lists because of the variance in size. In some cases this space would be unacceptably large. The last row in this scenario also acts as a sort of 'tail', and often there will be only one or two items in the last row which may also be undesirable.

Finally, I have created a more complex function, which checks how many items there are in total and attempts to create a 'target' height which is the total number of items divided by the number of columns. It then finds a reasonably good distribution for the items - this works by moving the largest list into the column and then looping through the rest of the lists to see if any will fit in the remaining column height, so there would be quite a performance hit, particularly for larger lists. It also supports using approximated heights of items, as well as a value for the overhead height of each list (the total of the space above and below the items, including the heading) - this won't be accurate if the items wrap onto new lines, but you could improve the algorithm to judge whether this will happen. This is really another reason why a JavaScript solution would have been superior, as JavaScript can tell you the actual height of things, rather than estimating based on supplied values. You could use the algorithm here to implement an equivalent JavaScript function. But in some cases where you can predict the 'height' (or equivalent factor for the items you are grouping) then this would be totally appropriate:

<?php
/**
 * Float into compacted columns.
 */
function columns_float_compact_lists_html($lists, $number_of_columns, $item_height = 1, $overhead_height = 0) {
   $output = "";
   // Create an array of the heights of each list.
   $heights = array();
   foreach ($lists as $list => $items) {
      $heights[$list] = $overhead_height + (count($items) * $item_height);
   }
   // Sort the heights array from largest to smallest.
   arsort($heights);
   // Set the target height of one column.
   $target_height = array_sum($heights) / $number_of_columns;
   // Create an array to store which list goes into which column.
   $columns = array();
   // Build the columns.
   for ($column = 0; $column < $number_of_columns; $column++) {
      // Ensure there are items still remaining.
      if (!empty($heights)) {
         // Create a tracker for the remaining space in the column.
         $remaining_space = $target_height;
         // Add the largest list to the column first.
         do {
            reset($heights);
            $list = key($heights);
            // Adjust $remaining_space, remove data from $heights, and add data to $columns.
            $remaining_space -= $heights[$list];
            unset($heights[$list]);
            $columns[$column][$list] = $lists[$list];
         } while ($remaining_space > reset($heights) && !empty($heights));

         // If there is space left in the column, find the best list to add.
         if ($remaining_space > 0 && !empty($heights)) {
            $closest = array();
            foreach ($heights as $list => $height) {
               if (empty($closest)) {
                  $closest["list"] = $list;
                  $closest["height"] = $height;
               }
               else if (abs($remaining_space - $height) < $closest["height"]) {
                  $closest["list"] = $list;
                  $closest["height"] = $height;
               }
            }
            // Ensure height of what we are adding is no more than double the space remaining.
            if ($closest["height"] <= 2 * $remaining_space) {
               // Adjust $remaining_space, remove data from $heights, and add data to $columns.
               $remaining_space -= $closest["height"];
               unset($heights[$closest["list"]]);
               $columns[$column][$closest["list"]] = $lists[$closest["list"]];
            }
         }
      }
   }
   // Finally build the HTML.
   foreach($columns as $column) {
      $output .= "<div class=\"float-". $number_of_columns ."-columns\">\n";
      foreach ($column as $list => $items) {
         $output .= "  <div class=\"list-container\">\n";
         $output .= "    <h3>". $list ."</h3>\n";
         $output .= "    <ul>\n";
         foreach ($items as $item) {
            $output .= "    <li>";
            $output .= $item;
            $output .= "</li>\n";
         }
         $output .= "    </ul>\n";
         $output .= "  </div>\n";
      }
      $output .= "</div>\n";
   }
   return $output;
}
?>

It isn't 100% perfect, but if you wanted to find the optimal solution you would have to create a far more exhaustive algorithm that would check many different combinations of lists against each other.

Example usage:

print columns_float_compact_lists_html($example, 3);

This will be the output:

And here is an example using the extra parameters for the height:

print columns_float_compact_lists_html($example, 3, 21, 106);

So that means that each item is worth "21" height units, and each list carries a "106" unit height overhead - I worked these out by taking a screenshot of the lists in a test script and measuring the height in pixels using Photoshop, but those values might not apply on this page. In this case the output is identical as without using the extra parameters, so I won't show the output, but I have seen cases where it has changed the distribution slightly.

If you're interested in advanced theory regarding this type of programmatic challenge, read about the Knapsack Problem and Combinatorial optimization.