Java多集合笛卡尔积

笛卡尔乘积:
笛卡尔乘积是指在数学中,两个集合X和Y的笛卡尓积(Cartesian product),又称直积表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员.
假设集合A={a, b},集合B={0, 1, 2},则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}.

下面是Java8求解笛卡尔积的代码:

import java.util.ArrayDeque;
import java.util.Spliterators.AbstractSpliterator;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

/**
* 计算多个数组的笛卡尔积
* @author xiaowj
*
* @param <T>
* @param <C>
*/
public class Cartesian<T, C> extends AbstractSpliterator<C> {
    final T[][] dimensions;
    final int[] currentLocation;
    final BiFunction<C, T, C> combiner;
    final ArrayDeque<C> partialValues;

    /**
    * 构造方法
    * @param dimensions 二维数组,每个数组元素不能为null(队列需要通过null判断)
    * @param initialValue 初始化值
    * @param combiner 笛卡尔积元素间通过连接函数连接
    */
    protected Cartesian(T[][] dimensions, C initialValue, BiFunction<C, T, C> combiner) {
        super(
            Stream.of(dimensions).mapToLong(d -> d.length).reduce(Math::multiplyExact).orElse(0),
            SIZED | DISTINCT | IMMUTABLE);
        this.dimensions = dimensions;
        this.currentLocation = new int[dimensions.length];
        this.partialValues = new ArrayDeque<>(dimensions.length);
        this.combiner = combiner;
        this.partialValues.push(initialValue);
    }

    @Override
    public boolean tryAdvance(Consumer<? super C> action) {
        if (partialValues.isEmpty()) {
            return false;
        } else {
            // 填充维度
            //
            while (partialValues.size() <= dimensions.length) {
                int dim = partialValues.size() - 1;
                partialValues.push(
                    combiner.apply(partialValues.peek(), dimensions[dim][currentLocation[dim]]));
            }

            // partialValues栈顶是笛卡尔积的结果
            //
            action.accept(partialValues.pop());

            for (int dim = dimensions.length - 1; dim >= 0; dim--) {
                if (++currentLocation[dim] < dimensions[dim].length) {
                    break;
                } else {
                    partialValues.pop();
                    currentLocation[dim] = 0;
                }
            }

            return true;
        }
    }

    public static <T, C> Stream<C> productOf(
        T[][] dimensions, C initialValue, BiFunction<C, T, C> combiner) {
        return StreamSupport.stream(new Cartesian<>(dimensions, initialValue, combiner), false);
    }
}