c# - 匹配次数最多的子序列？

Question

给定一个二维数据数组，我如何找到具有最多匹配项的最大组合？

例子:

Cust #  Prod #C1      P1C1      P2C2      P1C2      P3C3      P1C3      P3C3      P4

(using haskell - couldn't figure out how do this easily in C# which is desired)The subsequences are:

    > subsequenc­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"]]

I want to find the a subsequence of X size with more than Y matches...

So for this example, the largest subsequence with more than one match is: ["P1", "P3"] - with 2 counts

Because the individual customer sequences are:

    C1 => ["P1, "P2"]    C2 => ["P1", "P3"]    C3 => ["P1", "P3", "P4"]

So there are two instances of ["P1", "P3"] in those sets.

My initial thought was to generate the subsequences and then match, but my data set is too large.

Note: My data set has 13000 unique combinations of 2D data so the subsequence approach either overflowed or never finished depending on the language.

EDIT: I am interested in the longest subset (not ordered)

EDIT: @Jimmy: if you add the following to your list I would have expected to see P1, P2, P4 as the result since it has the most customers with that basket. Your solution unfortunately does not work

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

编辑:@Eric Lippert

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

编辑:从商业角度来看，我想找到我的许多客户购买的最常出现的一篮子商品。我意识到很多，篮子的大小是模糊的 - 但这就是结果分析的用武之地。

Answer 1

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

给定 n 个集合:C1 ... CN，每个元素都由元素{P1 ... PN}

找到这些子集的 X 与至少 Y 个元素的交集。

找到这 N 个集合的最大子集交集的更复杂的问题是 NP-Hard(参见 proof)。

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

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