问题标签 [cartesian-product]

我试图弄清楚如何在给定以下信息的情况下找到所有组合：

我从一个 JSON 数据集开始：

我想弄清楚的是如何获取这个数据集，并在为每一行选择“Q”、“R”、“W”或“T”元素时生成所有可能的组合。

所以我希望我的最终结果是这样的

我使用 JSON 是因为我认为它是最容易可视化的，但有谁知道我如何在 c# 中实现这一点？

如果这还不够清楚，请告诉我，我很难弄清楚如何准确地问这个问题。

我刚刚开始涉足Factor。我想计算两个序列的笛卡尔积：

我想看到的是一系列序列：

当我使用这个cartesian-product词时，我得到一个序列序列：

我也试过[ 2array ] cartesian-map了，但我得到了同样的东西。最后，我尝试[ 2array ] cartesian-each了，但我将每一对单独推入堆栈。至少它是平的，但我希望它们都在一个阵列中。

我该怎么做呢？

我需要做一个表的笛卡尔积，但没有相同的行。我现在有：

但是对于有 1300 行的 T_Car 表，它需要将近 2 分钟。我尝试使用 OPTION (HASH JOIN) 和 OPTION (MERGE JOIN) 但这最终会出现错误：

由于此查询中定义的提示，查询处理器无法生成查询计划。在不指定任何提示且不使用 SET FORCEPLAN 的情况下重新提交查询。

有没有可能优化这个查询？

我想创建一个 Java 方法，它接受一个inputArray = Object[n][]，其中 n 可以是任何整数，并输出 n 个子数组的所有值之间可能的 n 大小组合的列表。下面是一个例子：

输入数组：（其中 Object=String 且 n=3）

期望的输出：

显然，我的方法中不能有一个固定的嵌套循环，因为我n事先并不知道。所以，我猜解决它的唯一方法是通过递归方法？有什么建议吗？

PS：我知道网站上有简单的组合相关的帖子。

我正在寻找一种二维组合算法......如果这是正确的措辞。我对 PHP 非常有经验，但对算法和高级数学没有经验，所以请多多包涵。

我有一组元素，我想将它们与另一组元素组合并计算所有可能的组合，以便之后进行分析。集合中元素的数量永远不会改变，两个集合总是有五个元素：

不知道这是否是正确的措辞，但我想查看Set 1 项目的所有组合，在 Set 2 的项目之间进行划分。两个集合中的所有元素只能在每种可能性中使用一次，并且 Set 1 元素可以在 Set 2 元素中组合在一起，因此我得到一个看起来像这样的结果数组（一些随机值作为示例）：

等等……那些价值观。欢迎对此提出任何反馈，特别是：

• 如何在 PHP 中编写这样的代码？通过递归函数？我是否使用笛卡尔积算法？
• 有多少种组合可能？5^10 ?
• 根据前一点：在 Web 应用程序中实时处理这些数据是否可行？如果我有 1000 万个组合，我想我可能需要事先进行计算，保存结果分析并在实时应用程序执行期间使用它？
• 有一些限制（例如：Set 2 items 'One', 'Two' and 'Three' should always have at least one item from Set 1）但无用的组合将在之后的分析过程中被丢弃，因此无需将其包含在组合算法，除非它可以通过在那时构建这些来减少计算时间？

我的问题可能不是很清楚，所以请问我是否需要提供更多或更好的信息。

提前致谢

2012 年 2 月 28 日更新

我已经尝试了我在互联网上找到的 Power Set 和笛卡尔积函数的 PHP 实现（这种东西有点超出我自己尝试和编码的能力）。所以当我执行这段代码时：

这是 powerSet 函数在 $powerset 中的内容：

这就是笛卡尔函数返回的内容：

所以它有点像我想要的，但不是最难的部分。它“单独”考虑组合并且不在 Set2 中分配 Set1，确保所有三个 Set2 项目都使用所有 Set1 项目。

• 我是否误解了这两个功能的使用？我想这是我对如何结合 Power Set 和笛卡尔积来实现我的结果没有正确理解的东西。我应该在 cartesian() 函数中调用 powerSet() 函数吗？
• 也许那些特定的 PHP 函数不能完全满足我的目的？我在这里找到了它们：
  • 电源组：http ://bohuco.net/blog/2008/11/php-arrays-power-set-and-all-permutations/
  • 笛卡尔积：使用 PHP 关联数组查找笛卡尔积

另一个更新：在没有编程参考的情况下重述问题

这个问题与我为战略游戏创建的分析工具有关。每次使用该工具时，玩家可以从大量单位中选择 5 个不同的单位。这些单元可以以多种方式与其他（静态）实体（我们称这些“池”）组合。如果将这些单位与某些池相结合，这些单位具有可能会或可能不会改善玩家策略的特征。例如：

• A单元喜欢在1号池，但不喜欢在2号池
• 单元 B 讨厌在池 1 中，除非单元 A 也在那里
• ETC..

该工具的目的是找到哪些单元进入哪个池的最佳组合。这些是规则：

• 从大约 50 个集合中总是选择 5 个不同的单元。所有这些单元都有不同的特性。
• 总是有相同的 5 个池。它们具有不同的特征，但池不是从更大的集合中选择的，它们总是相同的。
• 每个池可以包含多个单元，从 0 到 5。
• 每个单元只能在一个池中。

输入是：

• 5 个变量单位的列表：A、B、C、D、E
• 5 个静态池的列表：Pool1、Pool2、Pool3、Pool4、Pool5

根据上述规则，输出应该是这两个列表之间的所有可能组合。一些例子：

组合1

• 池 1：A
• 池 2：B
• 池 3：C
• 池 4：D
• 池 5：E

组合2

• 池 1：A、B、C
• 池 2：D
• 池 3：E
• 池 4：
• 池 5：

组合3

• 池 1：C
• 池 2：
• 池 3：A
• 池 4：B
• 第 5 组：D、E

组合4

• 池 1：
• 池 2：
• 第 3 组：A、B、C、D、E
• 池 4：
• 池 5：

ETC...

所以我想做的是：

1. 采用存在的所有可能的单元和池组合。
2. 遍历它们并根据单元和池之间的协同作用为组合分配“战略价值”。
3. 选取“策略价值”最高的前 10 个组合

第 2 步和第 3 步没有问题。我遇到的问题是生成池中单元的所有可能组合。

希望这是对问题的更清晰的描述

这是我遇到的问题的简化版本。假设我有一个向量

还有一个

我想提出以下矩阵：

这也称为笛卡尔积。我怎样才能做到这一点？

我有一些桌子：

不要怪我，这是一个现有的应用程序，我没有创建数据库并且无法触及结构，因为里面有太多的数据和依赖它的报告。我只是想按要求修改报告。

我做一个查询：

并给我带来了笛卡尔积。我想：

（然后在我按 suc、dep、sec 分组的报告上）

相反，我得到了：

等等。它带来了 ALL sucurs、ALL depart、ALLsection和有时重复emp。

我错过了一些东西，但不知道是什么。有什么线索吗？

我主要相信这个问题有一个答案，但对于我的生活来说，我无法弄清楚如何去做。

假设我有三组：

而且我知道如何计算笛卡尔/叉积，（在这个网站和其他地方，它到处都是）所以我不会在这里讨论。

我正在寻找的是一种算法，它允许我从笛卡尔积中简单地选择一个特定项目，而无需生成整个集合或迭代直到我到达第 n 个项目。

当然，我可以轻松地迭代这样的小示例集，但我正在处理的代码将使用更大的集。

因此，我正在寻找一个函数，我们称之为“CP”，其中：

答案是在 O(1) 时间内产生的，或多或少。

我一直在遵循这样的想法，即应该有可能（哎呀，甚至很简单！）计算我想要的 A、B、C 元素的索引，然后简单地从原始数组中返回它们，但是我的尝试为了使这项工作正确，到目前为止，嗯，没有奏效。

我正在使用 Perl 进行编码，但我可以轻松地从 Python、JavaScript 或 Java（可能还有其他一些）移植解决方案

由于我不太了解这些类型的算法的语言（即如何用谷歌搜索），我将只演示我正在寻找的内容：

我有一个三个数组（源数组的长度不相等）：

我想要这些数组的所有可能组合，其中：

• 每个源数组中的元素不超过一个。
• array1、array2、array3 的顺序永远不会被打破（ABC总是在之前xyz总是在之前123）。

所以结果是：

结果的顺序对我来说并不重要。

在 php 中工作，但类似的语言或伪代码当然可以。或者我只是对我应该查看哪些特定类型的排列/组合算法提出建议。

我想在 Haskell 中生成一个相当大但有限的笛卡尔积，然后我需要对其进行迭代（想想平均场模型的分区函数）。自然的事情就是使用sequence，像这样：

不幸的是，对于 large n，这不适合内存，length l例如，我一请求就用完了堆。我需要一种方法来懒惰地做同样的事情。我最终“重新发现”了 base-3 算术，就像这样，

（有效）但感觉就像重新发明轮子，而且它太具体了。生成产品的更好的懒惰方式是什么？