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');

Answer 3

The CS problem you are trying to solve

You should look into the Backpack Problem. The items to be 'inserted into the backpack' will be the LIs. Each LI will have a weight and value equivalent to its height. The backpack capacity should be half the sum of all the LI heights. Run an algorithm to solve the backpack problem and your LIs will be divided into two sets with heights as you've described.

Intuitive explanation

The backpack algorithm finds a subset of items such that the value is as large as possible, but the weight doesn't exceed the backpack capacity. But our weight and value of each LI is its height, and the backpack capacity is half the total height of all LIs combined.

So essentially what it will give us is a set of all LIs such that the height is as high as possible without exceeding 1/2 the total height. In the case where you should end up with two equal-height sets of LIs, this will be one of the sets. In the case where you should end up with two sets of LIs with different heights, the backpack problem solution will return the set with a smaller height (and the remaining, unchosen LIs would be the second set).

Solution

Try the code used here: http://rosettacode.org/wiki/Knapsack_problem/Bounded#JavaScript

Or if you want to roll your own (not recommended - why bother?): http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem

Answer 4

$("ul.first li").each(function() {
    if ($("ul.first").outerHeight() > $("ul.second").outerHeight()) {
        $(this).appendTo($("ul.second"));
    }
});

Use this jQuery code.