Equalize two ULs by height

Question

I have a case where I'm provided with one UL, and an unknown number of LIs. I'm looking to use JS to split the LIs into 2 ULs (I'm using jQuery). I'm able to split the ULs evenly by number of LIs, but I'd like to split it based on the height of each LI as well, so that both ULs are close to the same height.

Any help with this would be appreciated, I don't feel like I'm getting anywhere with the approach I started with.

Thanks.

EDIT: JS code I currently have. The HTML is just a straight UL/LI, each LI can be of varying height.

var $sections = $('div.subsection');

$sections.each(function(){
  var $section = $(this);

  var $list = $section.children('ul');
  var $items = $list.children('li');
  var itemCount = $items.size();
  var leftover = itemCount % 2;
  var itemsPerColumn = Math.floor(itemCount / 2);
  var $newList = $('<ul />');

  $items.each(function(){
    var $this = $(this);
    var index = $items.index($this);

    if (index >= (itemsPerColumn + leftover)) {
      $this.remove().appendTo($newList);
    }
  });

  $list.after($newList);

  _equalizeListHeights();

  function _equalizeListHeights(){
    var listHeight = $list.height();
    var newListHeight = $newList.height();

    if (listHeight > newListHeight){
      var $lastItem = $list.children('li:last');
      var lastItemHeight = $lastItem.height();

      if (listHeight - lastItemHeight > newListHeight + lastItemHeight){
        $lastItem.remove().prependTo($newList);
        _equalizeListHeights();
      }
    }
  }

});

Answer 1

You can do it via CSS:

.double_column_list li {float: left; width: 50%;}

<ul class="double_column_list">
    <li>Awesome Stuff Awesome Stuff Awesome Stuff Awesome Stuff Awesome Stuff</li>
    <li>Awesome Stuff</li>
    <li>Awesome Stuff</li>
    <li>Awesome Stuff</li>
</ul>

To get 3 column, set width: 33.333%, 4 column width: 25% and so on.

Of course, if you keep increasing the height of one li to a point where rest of the lis can't match, this would look bad. But then, that issue cannot be fixed through JS either.

http://jsfiddle.net/rQJQb/

Update: As pointed out by commenters, if list items are not sorted by height (i.e. height of any one list item in the middle may be bigger/smaller than the ones preceding it), a sorting is needed: http://jsfiddle.net/rQJQb/2/

Answer 2

I think I can at least see the approach here:

1. Calculate the total height of all the list items (total), and store all the individual heights
2. Calculate the height of one list (total / 2)
3. Determine an algorithm to sum a set of heights to come as as possible to total / 2, without exceeding it.
4. Put the elements with these heights into the first list, and put the rest into the second

Step 3 is the tricky bit. It's related to the Subset Sum Problem.

---

EDIT

Here's a brute-force algorithm which solves your problem. It doesn't run on window.resize, because that would be silly. If you want to see it change, resize the result window, then push run.

//Sum a jQuery wrapped array
$.fn.sum = function() {
    var total = 0;
    this.each(function() { total += this; });
    return total;
};
//Mask elements with a bitmask
$.fn.mask = function(mask) {
    return this.filter(function(i) {
        return (mask >> i) & 1;
    })
}

//Get the sizes, and sneakily return a jQuery object
var sizes = $('.first li').map(function() { return $(this).outerHeight() });

var total = sizes.sum();
var maxTotal = total / 2;

var best = {
    total: 0,
    mask: 0
}

for (var subsetMask = 1; subsetMask < (1 << sizes.length); subsetMask++) {
    //Sum all the heights in this subset
    var subsetTotal = sizes.mask(subsetMask).sum();

    //New optimal solution?
    if (subsetTotal > best.total && subsetTotal <= maxTotal) {
        best = {
            total: subsetTotal,
            mask: subsetMask
        };
    }
}

$('.first li').mask(best.mask).appendTo('.second');