匹配次数最多的子序列

本文关键字： | 更新日期: 2023-09-27 18:06:52

给定一个2d数组的数据，我如何找到最大的组合与最多的匹配?

的例子:<>之前cst # Prod #C1 P1C1 P2C2 P1C2 P3C3 P1C3 P3C3 P4之前

(使用haskell -不知道如何在c#中轻松做到这一点)子序列为:

<>之前>子序列- es ["P1" -，"P2"，"P3" -，" P4"] -=>[[],["P1"],["P2"],["P1"、"P2"],["P3"],["P1"、"P3"],["P2"、"P3"],["P1"、"P2"、"P3"],["P4"],["P1"、"P4"],["P2"、"P4"],["P1"、"P2"、"P4"],[P3, P4"],["P1"、"P3, P4"],["P2"、"P3, P4"],["P1"、"P2"、"P3, P4"]]之前

我想找到X大小的a子序列，有超过Y个匹配…

对于这个例子，有多个匹配的最大子序列是:["P1"， "P3"] -有2个计数

因为单个客户序列是:

<>之前C1 => [" p1， " p2 "]C2 => [" p1 "， " p3 "]C3 => [" p1 "， " p3 "， " p4 "]之前

在这些集合中有两个实例["P1"， "P3"]

我最初的想法是生成子序列，然后匹配，但是我的数据集太大了。

注释:我的数据集有13000个唯一的2D数据组合，因此子序列方法要么溢出，要么永远不会完成，这取决于语言。

EDIT:我对最长子集(非有序)感兴趣

EDIT: @Jimmy:如果您将以下内容添加到列表中，我预计会看到P1, P2, P4作为结果，因为该购物篮的客户最多。不幸的是，您的解决方案不起作用

    { "C4", new HashSet<string>(new[] { "P1", "P2","P4"})},
    { "C5", new HashSet<string>(new[] { "P1", "P2","P4"})},
    { "C6", new HashSet<string>(new[] { "P1", "P2","P4"})},

EDIT: @Eric Lippert

我的理想输出是每一个组合，每次它都是一个子集。然后我可以查询篮子中商品数量最少的最大篮子。

EDIT:为了从业务角度来看，我想找到我的许多客户购买的最频繁出现的一篮子商品。我意识到篮子的数量和大小是模糊的，但这正是对结果进行分析的地方。

匹配次数最多的子序列

这个问题可以表述如下(如果我没理解错的话):

给定n个集合:C1…CN, 元素{P1…PN}

求这些子集中X的一个至少有Y个元素的交集

更复杂的问题是NP-Hard(参见这个证明)。

你的问题也可能是NP-Hard或NP-complete(因为它看起来像是寻找最大交集问题的决策版本)。你将无法找到一个有效的方法来解决你的问题。

你应该查找最大子集相交问题的启发式，或者从一些类似(但不同)和更流行的问题中寻找灵感，例如集合覆盖问题。

您所拥有的与此类似1 a | 1 b | 1 c

2 a | 2 b

3 c | 3 d

相当于

abc | ab | CD

所以基本上你要解决的问题必须是其中之一1. 查找最大长度字符串2. 找到频率最大的字符串3.

将序列表示为向量，为该向量编写自定义比较函数，将它们添加到multiset中，同时保持计数。并且记住到目前为止遇到的最频繁序列的最大计数，还要记住插入的最长向量。

只回答最长子序列:

customer c = entryList[0].customer;
product p;
set s;
set largestSet = s;
for (every entry in entryList)
{
  if(c ! = entry.customer)
   {  
     c = entry.customer;
     if (s.size > largestSet.size)    largestSet = s;
     s.clear();
   }
   s.add(entry.customer)
}

似乎你正在寻找最长的成对子集。

这是一种蛮力的方法:

从元组(c,p)的列表开始，创建一个{c:set(p1,p2,p3)}的字典。

var dict = new Dictionary<string, HashSet<string>> {
    { "C1", new HashSet<string>(new[] { "P1", "P2"})},
    { "C2", new HashSet<string>(new[] { "P1", "P3"})},
    { "C3", new HashSet<string>(new[] { "P1", "P3","P4"})},
};
var max = from pair1 in dict
          from pair2 in dict
          where pair2.Key != pair1.Key
          let s = pair1.Value.Intersect(pair2.Value).ToArray()
          orderby s.Length descending
          select s;
Console.WriteLine(string.Join(",", max.First()));

输出:

P1,P3

似乎是一个O(N^3)算法。