首页 » 编程笔记 » 正文

实现多个数组的组合排序算法总结

项目背景

最近在做一个SEO的项目,需要处理关键词,简单的说就是基于深度学习实体识别技术对电商query进行实体的识别,然后制定一些组合规则重组实体标签形成新的query

实体识别技术不是这次讨论的重点,本文重点说下项目中涉及到的实体之前的组合排序,数据举例:

对于鞋场景,用户可能会搜索的query组合

人群 ["女士", "宝宝", "男士"]

风格  ["休闲", "运动", "加厚"]

品类  ["网鞋", "松糕鞋", "单鞋"]

根据算法排列组合后可能得到

女士休闲网鞋

女士运动单鞋

等等

那这个问题的实质其实就是一个多List集合的组合排序问题,解决方案

通用的方案,矩阵笛卡尔积计算

 

 概念解释

笛卡尔乘积(Cartesian product)

在数学中,两个集合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)。类似的例子有,如果A表示某学校学生的集合,B表示该学校所有课程的集合,则A与B的笛卡尔积表示所有可能的选课情况。A表示所有声母的集合,B表示所有韵母的集合,那么A和B的笛卡尔积就为所有可能的汉字全拼。

笛卡尔积的符号化为:

A×B={(x,y)|x∈A∧y∈B}

例如,A={a,b}, B={0,1,2},则

A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}

B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

 

代码实现

(1)将每个维度的集合的元素视为List,多个集合构成List

(2)将多维笛卡尔乘积的结果放到List result之中作为输出

(3)程序可以采用递归调用

@SuppressWarnings({ "rawtypes", "unchecked" })  
	public static List Dikaerji0(List<List> al0) {  
		List a0 =  al0.get(0);// l1  
		List result = new ArrayList();// 组合的结果  
        for (int i = 1; i < al0.size(); i++) {  
        		List a1 = al0.get(i);  
        		List temp = new ArrayList();  
            // 每次先计算两个集合的笛卡尔积,然后用其结果再与下一个计算  
            for (int j = 0; j < a0.size(); j++) {  
                for (int k = 0; k < a1.size(); k++) {  
                		List cut = new ArrayList();  
  
                    if (a0.get(j) instanceof List) {  
                        cut.addAll((ArrayList) a0.get(j));
                    } else {  
                        cut.add(a0.get(j));  
                    }  
                    if (a1.get(k) instanceof List) {  
                        cut.addAll((ArrayList) a1.get(k));  
                    } else {  
                        cut.add(a1.get(k));  
                    }  
                   // System.out.print(cut);
                    temp.add(cut);  
                }  
            }  
            a0 = temp;  
           
            if (i == al0.size() - 1) {  
                result = temp;  
            }  
        }  
        return result;  
    }  

如果对于矩阵标准的3X3的这种 可以采用递归调用,代码更简洁
注意下面代码不适用于 [a,b,c] [1] [x,y] 这种长度不固定的矩阵集合

class Test{
      private static String[]  eachDfsResult;
      private static List  dfsResults; 

      private static void dfs(List<List> arr, int depth){
	if(arr != null && arr.size()>0) {
		for(int i = 0; i<arr.size();i++){
				
			 eachDfsResult[depth] = arr.get(depth).get(i).toString();
			 if(depth != (arr.size()-1)) {
				dfs(arr, depth + 1);
			 }else{
				dfsResults.add(StringUtils.join(eachDfsResult, "|"));
			 }	
				
		}
	}
       }
}

到此就完成了需求

总结

当然也可以用最简单的多重循环实现,更简单,更容易理解, 但是我们遇到问题还是要多想一步,全面一些
如果矩阵集合是用户输入的,长度不固定,个数也不一定的情况下,循环显然就不灵活了
解决问题之前先把问题抽象看看,有没有通用成熟的算法或者方案可以借鉴
以上实现我也是在网上找了一些 然后自己用java代码修改实现
希望对你有帮助