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).
if (o instanceof Set) {
          Set<?> s = (Set<?>) o;
          return s.size() == size && index.keySet().containsAll(s);
        }
        return false;
      }
      @Override
      public Iterator<Set<E>> iterator() {
        return new AbstractIterator<Set<E>>() {
          final BitSet bits = new BitSet(index.size());
          @Override
          protected Set<E> computeNext() {
            if (bits.isEmpty()) {
              bits.set(0, size);
            } else {
              int firstSetBit = bits.nextSetBit(0);
              int bitToFlip = bits.nextClearBit(firstSetBit);
              if (bitToFlip == index.size()) {
                return endOfData();
              }
              /*
               * The current set in sorted order looks like
               * {firstSetBit, firstSetBit + 1, ..., bitToFlip - 1, ...}
               * where it does *not* contain bitToFlip.
               *
               * The next combination is
               *
               * {0, 1, ..., bitToFlip - firstSetBit - 2, bitToFlip, ...}
               *
               * This is lexicographically next if you look at the combinations in descending order