考虑以下形式的排列列表（与顺序相关的组合）：

我需要为这个排列组找到最少数量的生成集。例如，鉴于上述排列，

不是最优解。最优解是 (1,5 2 3,4)。

您会注意到此解包含集合 A={1, 5} B={2} 和 C={3,4} 排列的原始列表是这些集合的有序笛卡尔积：AXBX C。

我想将排列列表划分为尽可能少的组，表示为集合 A、B 和 C，其乘积包含列表中的所有排列。最终的答案通常是（但不总是）一组集合列表，因为并不总是可以将排列列表减少到单个生成集列表。也就是说，通常情况下，集合 A、B 和 C 的乘积说明了列表中的某些排列，但集合 D、E 和 F 需要说明列表中的其他排列，依此类推.

我解决这个问题的粗略尝试包括检查我是否在列表中的两个排列槽中的任何一个上匹配并递归地合并它们。如果是这样，我合并了这两种组合，即

生产

不幸的是，这种组合的合并顺序不是关联的。一个理想的解决方案是以这样一种方式合并这些组合，即最终的集合列表将包含尽可能多的排列。

为了演示关联性问题，举这个例子，它不能减少到少于两个生成集列表：

假设您要根据以下规则递归地合并这些列，“如果任何两列匹配，我会通过按原样保留这些列来合并。然后我合并第三列中的两个集合以生成新集合。这两行合并后，我把原来的两行都扔掉了，所以没有重新合并，也没有重复计算。” 这些合并的顺序很重要。鉴于上面的排列列表，如果我合并 (1 2 3) 和 (1 2 4)，我得到 (1 2 3,4)。现在，如何进行下一次合并以优化生成集？假设我查看 (1 2 5) 并看到它在两列上匹配 (1 2 3,4)，我执行合并并得到 (1 2 3,4,5)。一切似乎都很好。但是，然后我将 (5 2 3) 和 (5 2 4) 合并为 (5 2 3,4)。我比较 (5 2 3,4) 和 (1 2 3,4,5)。我没有两列匹配，所以我停止合并。

现在假设我以不同的顺序合并。我合并 (1 2 3) 和 (1 2 4) 以产生 (1 2 3,4)。然后我合并 (5 2 3) 和 (5 2 4) 以产生 (5 2 3,4)。我看到我在这两个产品之间有一个匹配。然后我合并 (1 2 3,4) 和 (5 2 3,4) 以产生 (1,5 2 3,4)。发电机组的最终列表是 (1,5 2 3,4) 和 (1 2 5)。所以你看到合并顺序产生了两个不同的答案：(1,5 2 3,4) 和 (1 2 5) 与 (5 2 3,4) 和 (1 2 3,4,5)。

在这种情况下，我可能会选择任何一个答案，因为在每个答案中都会出现相同数量 (2) 的发电机组列表。但是，(1,5 2 3,4) 和 (1 2 5) 稍微更可取，因为 (1,5 2 3,4) 包含尽可能多的组合。然而，假设我们有一个包含 900 个组合的列表。问题的自下而上解决方案的合并顺序将导致您以非最佳方式减少问题，其中优化是集合列表中可能的最小计数。如果不查看所有可能的合并路径，很难知道合并顺序是什么，这并不比寻找匹配的蛮力方法更有效，我也尝试过这种方法。

我也尝试过蛮力方法。为什么蛮力法的效率让人无法接受？该方法首先在所有列中找到唯一整数列表。然后它生成这些整数的每个可能组合的幂集。它对列/集 A、列/集 B 和列/集 C 执行此操作。然后按大小对这些集进行排序（从大到小），计算每个集在其他列中的所有其他集之间的笛卡尔积，然后它循环遍历这些笛卡尔积，这些笛卡尔积由它们的生成集键入，以检查笛卡尔积是否与输入中的排列列表匹配。这大约是 O(n^3)，其中 n=输入列表中的组合数。如果我什至可以在 O(n^2) 中做到这一点，与现在相比，这将是一场胜利。

就内存考虑而言。假设每个插槽的域是整数 1-12。三个插槽中不同组合的数量为 12!/3! 您正在查看超过 7900 万种原始组合。那是在它们甚至被 Google 的 Guava Collection API 划分为集合之前（我强烈推荐 BTW）。我们可能会以某种方式懒惰地生成集合，我感觉 Google 会这样做，但内存限制仍然很大。

我真的在寻找一种算法来解决这个问题。但是，如果有一个 Java 库或方法可以以最小的痛苦解决这个问题，我也愿意。谢谢。

高水平

我正在尝试折叠句子列表中的常见子字符串，并仅显示它们不同的区域。所以采取这个：

并返回：

更多细节

• 我一直在研究最长的公共子串算法，但这似乎只比较两个字符串。
• 我只对比较字符串中的整个单词感兴趣。
• 只想从左到右评估字符串。
• 不常见子串的长度不会是相同的词数（“猫”与“花园蛇”）

我正在寻求有关算法的帮助。我相信这是 LCS 问题的变体，我认为是对后缀树的某种处理。可以解释和实现的伪代码将是理想的。

另一个例子

变成：

也许这种方法

这种方法怎么样...

我正在寻找第一个公共子字符串的实现

使用最长的公共子串实现（并忽略标点符号），你会得到“我认为你很棒”，但我正在寻找第一个出现的公共子串，在这个例子中：

也许是一个实现，它生成并排序了所有常见子字符串的列表，我可以从中获取第一个。

编辑

被比较的标记将是完整的单词。寻找第一个最长的整个单词序列的贪婪匹配。（假设在方法中使用了后缀树，树的每个节点都是一个词）

从集合论：

如果 A∩B = {}，则集合 A,B 完全不相交

其中 {} 是空集。

参考：具有通用集合的基本集合论，Randall Holmes

此外，它说；

说不相交集 A 和 B “没有交集”是不正确的；他们确实有一个交集，即空集，但这个交集没有元素

如果 A 和 B 不相交，那么A∩B = B∩A = {}

在 C# 中：

为什么？

如果==只是比较对象的 Id（相反；如果a是b；不是isC# 的运算符），有没有办法表示实际Empty Set？

我正在制作一个密码暴力破解工具作为学习练习，我希望它可以恢复。

所以，我想要说的是，这是一组可能的字符，如果我计算这个集合的每个可能组合的笛卡尔集合，长度为 n，那么点 x 的集合是什么？

但是，我想在不计算整个集合的情况下做到这一点。我在网上的一个地方看到过类似的逻辑，但我无法将其概括为适合。

任何帮助都会很棒，谢谢！如果有帮助，我精通 C#。

编辑：这是我之前提到的问题：如何从笛卡尔积中选择特定项目而不计算其他所有项目

编辑：这是我的意思的一个例子：

因此，如果我要搜索 4 的集合，我会得到 [aaad]。但是，如果我正在搜索元素 7000，则需要很长时间才能到达该点。

我正在制作一个工具，它使用笛卡尔积运算来计算每个可能的密码，给定一组可能的字符和长度。

因此，一个源集可能在一个数组中包含 0-10、az 和 AZ，总共 62 个字符。

长度为 4 时，笛卡尔积将包含 4^62 个密码，长度均为 4。

给定一个源字符串，即“a9BZ”，我是否有可能计算出笛卡尔积中会出现什么点？

我有一种方法可以将value转换为长度length的newBase数。

英文的逻辑是：

虽然下面的方法确实工作得很好，因为使用了非常大的数字，它可能需要很长时间才能完成：

例如 value=(((65536^480000)-1)/2), newbase=(65536), length=(480000) 在 64 位架构，四核 PC 上大约需要一个小时才能完成。

我的问题是，如何将此方法更改为允许多个线程计算部分数字的方法？

我正在使用 C#，但如果你不熟悉它，那么伪代码也可以。

注意：该方法来自这个问题：Cartesian product subset returns set of most 0

我有一个需要在可变数量的键上调用 zunionstore 的 lua 脚本。我正在尝试执行以下代码：

重要的几行是：

它构建了键列表和实际调用：

但是，执行时出现以下错误：

那么，如何将在 lua 脚本中计算的可变数量的键传递给 redis.call("zunionstore"...) 命令？

提前致谢！

我试图只返回一组子项包含多个特定记录的父项。鉴于此表：

我想找到Product既有AZ子记录又有CA子记录的列表，即使它还有其他记录。哪个会返回...

• 有 N 个孩子和有限的 T 组可区分的玩具；
• 每个孩子都喜欢所有玩具的特定子集 T _i；
• 每个孩子都需要拥有一个确切的数字 t _i <= |T _i | 玩具，但仅限于孩子喜欢的玩具；
• 有些玩具不止一个孩子喜欢。
• 一个玩具不能由多个孩子拥有

可能有很多方法可以满足每个孩子对玩具的需求。

问题：给定 N、{T _i }、{t _i } 和一个种子 RNG，从儿童拥有的玩具的所有可能配置中，我需要选择一个均匀分布（或至少接近均匀分布）的配置，即从儿童映射到他们拥有的玩具。

生成所有可能的配置并选择第 j 个配置是行不通的——可能会有很多配置。

在下面的示例中，有 4 个孩子：红色、蓝色、绿色和黄色。红色需要拥有4个玩具，蓝色——5个，绿色——3个，黄色——3个。孩子喜欢的玩具在对应颜色的长方形里面。

因此，我需要的是生成分布良好的算法大纲Map<Child, Set<Toy>>，或者任何有助于阅读以解决问题的链接。