问题标签 [cartesian-product]

有两个表：表 A 和表 B。它们具有相同的列，并且数据实际上是相同的。它们都具有自动递增的 ID，两者之间的唯一区别是它们对于相同的记录具有不同的 ID。

在这些列中，有一个 IDENTIFIER 列不是唯一的，即两个表中有（非常少）具有相同 IDENTIFIER 的记录。

现在，为了找到表 A 的 ID 和表 B 的 ID 之间的对应关系，我必须在 IDENTIFIER 列上连接这两个表（出于所有目的，它是自连接），如下所示：

但是，由于 IDENTIFIER 不唯一，这会生成 IDENTIFIER 重复值的所有可能组合，我不希望这样。

理想情况下，我想根据它们的顺序在具有重复 IDENTIFIER 值的 ID 之间生成一对一的关联。例如，假设表 A（因此在表 B）中有 6 条 ID 不同但 IDENTIFIER 值相同的记录：

那将是理想的。无论如何，无论 ID 的顺序如何，一种生成一对一关联的方法仍然可以（但不是首选）。

谢谢你的时间，

西尔维奥

我正在寻找一个示例，说明如何在 Ruby、类似 C 的语言或伪代码中创建可变数量的整数数组的笛卡尔积，每个数组的长度不同，并以特定顺序逐步执行结果：

因此，[1,2,3],[1,2,3],[1,2,3]：

而不是我看到的典型结果（包括我在下面给出的示例）：

此示例的问题在于，在尝试前两个位置的所有组合之前，根本不会探索第三个位置。在使用它的代码中，这意味着即使正确答案通常是（大得多的）1、1、2，它也会检查几百万个可能性，而不是在找到它之前只检查几千个。

我正在处理一百万到数亿的结果集，因此在这里生成它们然后排序是不可行的，并且会破坏在第一个示例中对它们进行排序的原因，即尽快找到正确的答案并因此中断早于笛卡尔积生成。

以防万一它有助于澄清上述任何内容，这就是我现在如何执行此操作（这具有正确的结果和正确的性能，但不是我想要的顺序，即它会创建上面第二个清单中的结果）：

更新：我没有说得很清楚，我正在寻求一个解决方案，其中在添加 3 之前检查 1,2 的所有组合，然后是所有 3 和 1，然后是所有 3、2 和 1，然后是所有 3 ,2。换句话说，在“垂直”之前“水平”探索所有早期的组合。探索这些可能性的确切顺序，即 1,1,2 或 2,1,1，并不重要，只是在混合 3 之前探索了所有 2 和 1，依此类推。

我遇到了一个特定的问题，并为它寻找一些算法。要解决的问题如下所述。

假设我们有如下组合

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

这些组合是从给定的集合中生成的，在这种特殊情况下，让我们说

{1},{3,4,8},{5}

{2,3},{4},{5}

{2}、{4}、{7}

我想做的是从这些组合中重新创建集合。我知道对于这些组合，您有不止一种解决方案，例如

第一个解决方案

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

第二种解决方案

{1}、{3、8}、{5}

{1、2、3}、{4}、{5}

{2}、{4}、{7}

第三个解决方案

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

但是最终（最佳）解决方案将是具有尽可能少的集合的解决方案，或者是随机解决方案，以防它们在集合计数方面都相等。

是否存在针对此类问题的算法？如果任何一直在处理此类问题的人可以给我一些提示，我将不胜感激。

编辑：看起来我正在寻找的是 n 元积的分解（N 的笛卡尔积）

编辑：在对该主题进行更多研究后，我发现该问题在“图论”中被称为“最小集团覆盖”问题

问候，巴兹

在阅读 MySQL 连接命令的文档时，看起来所有这些joins都类似于,通过简单地找到笛卡尔积然后从该结果中进行选择。
这是一个准确的假设吗？
我是否应该编写自己的子查询并从中进行选择？

我在弄清楚如何生成锯齿状数组的笛卡尔积时遇到了一些麻烦。我已经用谷歌搜索了，但我似乎找不到迭代语言的实现。所以我试图自己弄清楚，但我遇到了一个障碍。让我们更清楚地定义问题

假设我有一个看起来像这样的数组数组

我如何从那个到

编辑：现在这只是一个例子，第一个数组可以包含动态数量的数组，每个数组都是动态大小的。

如果 x 是外部数组中的元素数，并且 y[] 是长度为 x 的动态数组，则元素包含内部数组中的元素数。那么 A 的 x 变成 B 的 y，B 的 x 是 y 在 A 中的乘法和。（未证明，从示例中假设）

由于 A 的 x 是动态的，因此该函数必须是递归的。这是我的尝试。

这是我所得到的。递归函数建立一个a[递归深度]的一个元素的临时数组，然后当它达到最大深度时，它分配那个B，并增加Bs迭代器，回溯并选择a[递归深度]的下一个元素，等C。

问题是段错误，我不知道为什么。

亲爱的，给定一个变量，比如说，三个值，我试图生成所有可能的组合，比如这些变量的三元组。

虽然这段代码可以解决问题，

它有点，嗯，笨拙，如果我尝试对三个以上变量的组合做同样的事情，只会变得更糟

因此，我的 Python 101 问题：

1. 如何使用迭代器重写上面的代码？我的意思是，是否有可能有一个迭代器来产生上述“状态”的元素？

2. 是否可以将其扩展为不仅生成三胞胎，还生成 4-plet、5-plet 等？

正如标题所述，Ruby 是否允许笛卡尔积类型？我在任何地方都找不到任何东西。

谢谢

我有一个像这样的类结构：

有一个人。他有1..n条狗。每只狗有 1..n 只小狗。

我想要一份所有可能的小狗组合的清单，从每只狗中取出 1 只小狗。例如：

狗 1 小狗 A，狗 2 小狗 A 狗 1 小狗 A，狗 2 小狗 B 狗 1 小狗 B，狗 2 小狗 A 狗 1 小狗 B，狗 2 小狗 B

如果它在 sql 表中，我会执行以下操作来“乘以”表：

有没有一些linq-ish方式来做这种事情？？？

非常感谢

我希望在 Haskell 中生成 2 个列表的笛卡尔积，但我不知道该怎么做。笛卡尔积给出了列表元素的所有组合：

这不是一个实际的家庭作业问题，也与任何此类问题无关，但解决此问题的方式可能对我遇到的问题有所帮助。

我想生成给定数量向量的元素的所有可能组合。

例如，对于，[1 2]我想生成元素：[1 2][4 5]

[1 1 4; 1 1 5; 1 2 4; 1 2 5; 2 1 4; 2 1 5; 2 2 4; 2 2 5]

问题是我不知道需要计算组合的向量数量。在这种情况下可能有 3 个，或者可能有 10 个，我需要一个概括。你能在 MATLAB 中帮我解决这个问题吗？是否已经有可以执行此任务的预定义函数？