'多个集合排列组合'

笛卡尔乘积

1.两个集合,组成新的集合.

处理的思想:
1.从一个集合中,取出一个元素. 这个元素与另外的一个集合做一次组合.组成新的集合.
第一个集合遍历完成,则组合完成.

即记第一个集合的长度是M ,另一个集合的长度是N.
则需要遍历的次数是M*N .
因为集合1中的每一个元素,都需要遍历N次.

而笛卡尔乘积亦是M*N

2.多个集合,组成的笛卡尔乘积.

这里有两种思路:
第一种是采用递归.
第二种是采用循环.

原理上来说,我的解决思路是多个集合的笛卡尔乘积拆分成2个笛卡尔乘积的运算.
每次都是当前的集合与下一个集合做2个迪卡而乘积运算.

递归的写法是写一个处理2个集合的方法,然后有条件的递归调用.递归写起来比较简单.

循环的思想,可以考虑采用栈.

使用场景

笛卡尔乘积使用场景还是很多的,例如组合排列.商品sku.等等

示例代码:

/**
 * 数据组装:递归处理
 * <p>
 * 思路:从第一层取出该层所有元素,与下一层的每一个元素拼接.组成中间变量,继续拼接下一层.直到层数拼接完成.
 * 这时候,该层的所有数据已完成拼接.则返回拼接数据的list.
 *
 * @param layer     层
 * @param nowString 当前组合的中间变量
 * @param lists     待组合的所有数据,
 * @return
 */
private static List<String> fxEachShangPin(int layer, String nowString, List<List<ShangPin>> lists) {
    List<String> strings = new ArrayList<>();
    if (layer < lists.size()) {//有下一个List
        List<ShangPin> nextList = lists.get(layer);
        for (int i = 0; i < nextList.size(); i++) {
            ShangPin subShangPin = nextList.get(i);
            String tmpStr = subShangPin.getSpName();
            //当前层级与下一层级组装
            if (StringUtils.isNotBlank(nowString)) {
                tmpStr = nowString + "-" + tmpStr;
            }
            List<String> subStr = fxEachShangPin(layer + 1, tmpStr, lists);
            strings.addAll(subStr);
        }
        return strings;
    } else { //没有下一层
        return Lists.newArrayList(nowString);
    }
}

    /**
 * 使用循环来解决,有栈的思想
 *
 * @param lists
 * @return
 */
private static List<String> fxStackShangPin(List<List<ShangPin>> lists) {
    if (CollectionUtils.isEmpty(lists)) return new ArrayList<>();

    List<String> rs = new ArrayList<>();
    List<String> tmpList = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    while (stack.size() != 0) {
        Integer layer = stack.pop();
        List<ShangPin> shangPins = lists.get(layer);
        if (CollectionUtils.isEmpty(shangPins)) continue;
        //初次塞值
        if (CollectionUtils.isEmpty(rs)) {
            for (int i = 0; i < shangPins.size(); i++) {
                ShangPin shangPin = shangPins.get(i);
                if (shangPin == null) continue;
                tmpList.add(shangPin.getSpName());
            }
        }
        //二级数据组装
        if (!CollectionUtils.isEmpty(rs)) {
            for (int i = 0; i < rs.size(); i++) {//数据组装
                String s = rs.get(i);
                for (int j = 0; j < shangPins.size(); j++) {
                    ShangPin shangPin = shangPins.get(j);
                    if (shangPin == null) continue;
                    String tmp = shangPin.getSpName();
                    if (StringUtils.isNotBlank(s)) {
                        tmp = s + "-" + shangPin.getSpName();
                    }
                    tmpList.add(i, tmp);
                }
            }
        }
        //临时变量传递
        rs.clear();
        rs.addAll(tmpList);
        tmpList.clear();
        layer++;
        //下一层级
        if (layer < lists.size()) {
            stack.push(layer);
        }
    }
    return rs;
}

---

End