问题标签 [cartesian-product]

Given the following string:

"foo bar-baz-zzz"

I want to split it at the characters " " and "-", preserving their value, but get all combinations of inputs.

i want to get a two-dimensional array containing

Is there any built-in method in Java to split the string this way? Maybe in a library like Apache Commons? Or do I have to write a wall of for-loops?

以下 SQL 将返回每个BT.Bt_Name为L.date_backNull 的位置。我只想选择重复的BT.Bt_NamesL.Bc_id

COUNT(L.Bc_id)对于所有为 NULL 的记录，连接是否导致大于 1 L.Date_back？仅供参考，应该只返回一个（故意输入错误）。

我想计算Java 中任意数量的非空集的笛卡尔积。

我已经写了那个迭代代码......

...但我发现它相当不雅。有人有更好的，仍然是迭代的解决方案？一个使用一些很棒的函数式方法的解决方案？否则......关于如何改进它的建议？错误？

有人可以为我演示一种比我目前使用的更有效的笛卡尔积算法（假设有一个）。我环顾四周，用谷歌搜索了一下，但看不到任何明显的东西，所以我可能会遗漏一些东西。

这是我在代码中所做的高度简化的版本。这两个整数是用于检索一个/多个对象的查找键，并且来自两个查找的所有对象都配对在一起成为新对象。

在一个更大更复杂的系统中的这个小代码块成为一个主要的性能瓶颈，因为它在规模上运行的数据集。通过改进用于存储对象的数据结构和所涉及的查找，其中一些可能会得到缓解，但我认为主要问题仍然是笛卡尔积本身的计算。

编辑

因此，有关我对该算法的具体用法的更多背景信息，看看是否有任何技巧可以用来回应 Marc 的评论。整个系统是一个 SPARQL 查询引擎，它处理对图数据集的 SPARQL 查询，SPARQL 是一种基于模式的语言，因此每个查询都包含一系列与图匹配的模式。在两个后续模式没有公共变量（它们是不相交的）的情况下，有必要计算两个模式产生的解决方案的笛卡尔积，以获得整个查询的可能解决方案集。可能有任意数量的模式，我可能必须多次计算笛卡尔积，如果查询由一系列不相交的模式组成，这可能导致可能的解决方案出现相当指数的扩展。

不知何故，从现有的答案中，我怀疑是否有任何技巧可以适用

更新

所以我想我会发布我实施的更新，以尽量减少对笛卡尔积的需求，从而优化查询引擎。请注意，并非总是可以完全消除对产品的需求，但几乎总是可以进行优化，因此要连接的两个集合的大小要小得多。

由于作为一组三重模式的每个 BGP（基本图模式）都作为一个块（本质上）执行，因此引擎可以自由地在 BGP 中重新排序模式以获得最佳性能。例如，考虑以下 BGP：

按原样执行查询需要笛卡尔积，因为第一个模式的结果与第二个模式不相交，因此前两个模式的结果是它们各自结果的笛卡尔积。这个结果将包含比我们实际需要的更多的结果，因为第三个模式限制了第一个模式的可能结果，但是我们直到之后才应用这个限制。但是如果我们像这样重新排序：

我们仍然需要笛卡尔积来获得最终结果，因为第 2 和第 3 模式仍然不相交，但是通过重新排序，我们限制了第 2 模式结果的大小，这意味着我们的笛卡尔积的大小会小得多。

我们还进行了一些其他优化，但我不打算在这里发布它们，因为它开始对 SPARQL 引擎内部进行相当详细的讨论。如果有人对更多细节感兴趣，请发表评论或给我发推文@RobVesse

我一直在尝试解决这个问题一段时间，但一直未能找到一个好的解决方案。开始：

给定多个集合：

我想从集合列表中生成所有可能的序列。在这个例子中，序列的长度是 5，但它可以是大约 20 左右的任何长度。对于位置 1，可能的候选者分别是“A”和“T”，对于位置 2，唯一的选项是“C”，所以在。

上面例子的答案是：

ACATG, ACCTG, ACGTG, TCATG, TCCTG, TCGTG

我在 ruby​​ 中执行此操作，并且我将不同的集合作为主数组中的数组：

起初我认为递归解决方案是最好的，但我无法弄清楚如何正确设置它。

我的第二个想法是创建另一个相同大小的数组，每个数组都有一个索引。因此 00000 将对应于“ACATG”上方的第一个序列，而 10200 将对应于“TCGTG”。从 00000 开始，我会将最后一个索引增加 1，并将其与相关集合的长度取模（set1 为 2，set2 为 1），如果计数器环绕，我会将其归零并将前一个索引增加一个。

但是我对这个解决方案的思考越多，对于这个非常小的问题来说似乎太复杂了。必须有一个我缺少的更直接的解决方案。谁能帮帮我？

/缺口

我有一个列表 L = [a, b, c] 并且我想生成一个元组列表：

我试着做 L * L 但它没有用。有人可以告诉我如何在 python 中得到这个。

这个问题询问如何计算给定数量向量的笛卡尔积。由于向量的数量是预先知道的并且相当少，因此使用嵌套的 for 循环很容易获得解决方案。

现在假设以您选择的语言给您一个向量向量（或列表列表或集合集等）：

如果我被要求计算它的笛卡尔积，那就是

我会继续递归。例如，在 quick&dirty python 中，

有没有一种简单的方法来迭代计算它？

（注意：答案不需要在 python 中，无论如何我知道在 python 中 itertools 做得更好，就像在这个问题中一样。）

我想在 Perl 中进行排列。例如，我有三个数组：["big", "tiny", "small"]然后我还有["red", "yellow", "green"]and ["apple", "pear", "banana"]。

如何得到：

我知道这称为排列。但我不知道该怎么做。另外我不知道我可以拥有多少个数组。可能有三四个，所以我不想做嵌套循环。

我一直在尝试做一个返回 n 个集合的笛卡尔积的函数，在 Dr Scheme 中，集合作为列表列表给出，我整天都被困在这个问题上，我想要一些指导方针开始。

----以后编辑-----

这是我想出的解决方案，我敢肯定它不是迄今为止最有效或最整洁的，但我只学习了 3 周的 Scheme，所以请放轻松。

seqClojure中是否有一个很好的算法可以同时计算三个s的笛卡尔积？

我正在从事 Clojure 的一个小型业余项目，主要是作为学习该语言及其并发特性的一种手段。在我的项目中，我需要计算三个seqs 的笛卡尔积（并对结果进行处理）。

我在 中找到了这个cartesian-product功能clojure.contrib.combinatorics，效果很好。然而，笛卡尔积的计算结果证明是程序的瓶颈。因此，我想同时执行计算。

现在，对于这个map函数，有一个方便的pmap替代方法可以神奇地使事情并发。这很酷:)。不幸的是，这样的事情不存在cartesian-product。我已经查看了源代码，但我找不到一种简单的方法让它自己并发。

另外，我尝试自己使用 实现一个算法map，但我想我的算法技能已经不像以前那样了。我设法为两个 s 想出了一些丑陋的东西seq，但三个绝对是一座太远的桥梁。

那么，有没有人知道一种已经并发的算法，或者我可以自己并行化的算法？

编辑

换句话说，我真正想要实现的是实现类似于以下 Java 代码的东西：