二维数组交叉组合算法

原创
2016/01/09 16:06
阅读数 2.8K

一、名词解释

  • 1、多维:描述一个实体的不同属性,如:颜色、尺寸、价格

  • 2、散列:每个属性有多个属性值,且数量不一

  • 4、分组:对属性值进行组合,不可出现完全相同组合,且每组数量必须等于属性个数,用来表明一个唯一实体

  • 3、交叉组合:每个属性中分别取值进行组合,顺序不受限制,必须保证每种可能性都有出现

  • 4、原子:每个属性中具体值

二、变量定义说明

  • 1、原子的出现次数 = $times

  • 2、属性值个数 = $valCount

  • 3、属性个数 = $attrCount

  • 4、最长分组数 = $groupCount

  • 5、出现最多次原子,的出现次数 = $maxTimes

  • 6、组 = $group

  • 6、组集合 = $groups

三、算法分析

  • 1、原子出现次数$times;计算方式,连乘(数学表达式大约是这样):∏ $times = a1 * a2 * …… * an

  • 2、随意取,原子出现次数$maxTimes,及其对应属性的值个数$valCount

  • 3、计算,分组总数$groupCount = $times  $valCount

  • 4、递归进行列填充

    • 1)首列填充,每个属性值按照出现次数填充新的列表

    • 2)其他列填充,分别针对其后面所有列表组合过程中出现次数计算,及分组数计算

  • 5、重组完成最终分组。

    • 1)遍历首列,取相应下标值,填充到组

    • 2)取其余每列对应下标(确定下标算法:分组总数列实际长度取余)值,填充到行

  • 6、将每组填充到组集合中

四、算法实现

package com.common.utils.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chh
 */
public class MultidimensionalArrayCrossGroup {

    /**
     * <p>重组完成最终分组</p>
     * 
     * @param arrayStr 属性列表
     * @return 组集合
     * @see MultidimensionalArrayCrossGroup#calculation(java.lang.String[][], java.lang.List);
     */
    public static List<String[]> calculation(String[][] arrayStr) {

        List<List<String>> columns = new ArrayList<>();
        calculation(arrayStr, columns);
        List<String> column = columns.get(0);
        List<String[]> groups = new ArrayList<>();

        for (int i = 0; i < column.size(); i++) {

            String[] group = new String[columns.size()];
            group[0] = column.get(i);

            for (int j = 0 + 1; j < columns.size(); j++) {

                List<String> values = columns.get(j);
                group[j] = values.get(i % values.size());
            }
            groups.add(group);
        }
        return groups;
    }

    /**
     * <p>列填充,递归</p>
     * 
     * @param arrayStr
     * @param columns
     * @see MultidimensionalArrayCrossGroup#calculation(java.lang.String[][])
     */
    public static void calculation(String[][] arrayStr, List<List<String>> columns) {
        List<String> column = new ArrayList<>();
        int k = columns.size();
        for (int i = 0; i < arrayStr[k].length; i++) {
            int times = 1;
            for (int j = k + 1; j < arrayStr.length; j++) {
                int valCount = arrayStr[j].length;
                times = times * valCount;
            }
            for (int j = 0; j < times; j++) {
                column.add(arrayStr[k][i]);
            }
        }
        columns.add(column);
        if (arrayStr.length > columns.size()) {
            calculation(arrayStr, columns);
        }
    }

}

五、算法测试

public class Test {
    public static void main(String[] args) {
        String[][] arrayStr = new String[4][];
        arrayStr[0] = new String[] { "红", "黄" };
        arrayStr[1] = new String[] { "2", "3", "4" };
        arrayStr[2] = new String[] { "A", "B", "C" };
        arrayStr[3] = new String[] { "A1", "B1" };
        List<String[]> groups = MultidimensionalArrayCrossGroup.calculation(arrayStr);
        for (int i = 0; i < groups.size(); i++) {
            System.out.println(JSON.toJSONString(groups.get(i)));
        }
    }
}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
9 收藏
1
分享
返回顶部
顶部