This was almost certainly my fault, but as I look at the implementation of Sets.cartesianProduct, I think its `contains` method made the assumption that `ImmutableSet.asList().indexOf` was O(1), which is no longer the case for Android.  It should probably get a specific `contains` implementation that actually is O(sets), not O(sets*setSize).
@Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
      return new FilteredSortedSet<E>(
          ((SortedSet<E>) unfiltered).subSet(fromElement, toElement), predicate);
    }
    @Override
    public SortedSet<E> headSet(E toElement) {
      return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate);
    }
    @Override
    public SortedSet<E> tailSet(E fromElement) {
      return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate);
    }
    @Override
    public E first() {
      return Iterators.find(unfiltered.iterator(), predicate);
    }
    @Override
    public E last() {
      SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered;
      while (true) {
        E element = sortedUnfiltered.last();
        if (predicate.apply(element)) {
          return element;
        }
        sortedUnfiltered = sortedUnfiltered.headSet(element);
      }
    }
  }
  @GwtIncompatible