问题标签 [cartesian-product]

这基本上就是我的程序正在做的事情：

如果您有 5 种不同的衬衫和 4 条不同的裤子可供选择，那么您可以穿 20 种不同的衬衫和裤子组合，我的程序将遍历所有 20 种组合以确定哪个是“最好的”穿。

除了，在我的情况下，有 11 种不同类型的服装（如头饰、手套、裤子、耳环、鞋子、斗篷等），每个类别多达 10 件。因此，可能有多达 11^10 种组合，当我尝试在每个类别中仅使用 4 个或 11^4 运行我的程序时，大约需要 5 秒才能完成。11^10 需要 DAYS 天。

目前，我正在进行的是 11 个嵌套在彼此内部的循环来遍历每个组合。这显然不是最好的方法，因为它太慢了。我怎样才能让它更快？对于上下文，我有 1 个“外部”ArrayList，其中包含 11 个 ArrayList，这 11 个 ArrayList 中的每一个都是一个对象列表（衣服）。

假设我有两组数字：

我想创建一个输出以下 6 种组合的算法（在 Java 中）：

每个组内可以有任意数量的组和任意数量的成员。所以在上面的例子中，有 2 个组，第一个组有 3 个成员，第二个组有 2 个成员。另一个示例如下（3 个组，第一组 3 个成员，第二组和第三组 2 个成员）：

这将产生以下 12 种组合：

我怎样才能在 Java 中做到这一点？我正在尝试使用递归，并且我已经看过一个类似的问题，但我仍然做不到。谢谢您的帮助！（PS这不是家庭作业）

有没有更好的方法来计算笛卡尔积。由于笛卡尔积是一种特殊情况，每种情况都不同。我想，我需要解释我需要实现什么，以及为什么我最终会做笛卡尔积。如果笛卡尔积是我问题的唯一解决方案，请帮助我。如果是这样，如何提高性能？

背景：

我们正在努力帮助客户以更便宜的价格购买产品。

假设客户订购了 5 种产品（prod1、prod2、prod3、prod4、prod5）。

每个订购的产品都由不同的供应商提供。

表示格式 1：

• 供应商 1 - 提供 prod1、prod2、prod4
• 供应商 2 - 提供 prod1、prod5
• 供应商 3 - 提供 prod1、prod2、prod5
• 供应商 4 - 提供 prod1
• 供应商 5 - 提供 prod2
• 供应商 6 - 提供 prod3、prod4

换句话说

表示格式 2：

• 产品 1 - 由 vendor1、vendor2、vendor3、vendor4 提供
• 产品 2 - 由 vendor5、vendor3、vendor1 提供
• 产品 3 - 由供应商提供 6
• 产品 4 - 由供应商 1、供应商 6 提供
• 产品 5 - 由供应商 3、供应商 2 提供

现在根据价格选择最好的供应商。我们可以按价格对产品进行分类并取第一个。

在这种情况下，我们选择

• 来自供应商 1 的产品 1
• 来自供应商 5 的产品 2
• 来自供应商 6 的产品 3
• 来自供应商 1 的产品 4
• 来自供应商 3 的产品 5

复杂：

由于我们选择了 4 个独特的供应商，我们需要支付 4 个运费。

此外，每个供应商都有一个最低采购订单。如果我们不满足它，那么我们最终也要支付这笔费用。

为了选择产品的最佳组合，我们必须对提供的产品进行笛卡尔积来计算总价格。

在我们的例子中

• {vendor1，vendor2，vendor3，vendor4}
• {供应商1，供应商3，供应商5}
• {供应商6}
• {供应商1，供应商6}
• {供应商2，供应商3}

需要计算 4 * 3 * 1 * 2 * 2 = 48 个组合以找到最佳组合。

• {vendor1，vendor1，vendor6，vendor1，vendor2} = totalprice1，
• {vendor1，vendor3，vendor6，vendor1，vendor2} = totalprice2，
• *
• {vendor4，vendor5，vendor6，vendor6，vendor3} = totalprice48

现在对计算的总价格进行排序以找到最佳组合。

实际问题：

如果客户订购的产品超过 15 种，并假设每种产品都由 8 个不同的供应商提供，那么我们最终会计算 8^15=35184372088832 组合，这需要几个小时以上的时间。如果客户订购超过 20 种产品，则需要几天以上的时间。

有没有办法从不同的角度解决这个问题？

我能够在C中实现静态数组数量的笛卡尔积。但是我想动态构建一个代码来获取输入数组的数量。有人可以阐明如何“仅使用数组”来做到这一点。如果不可能使用数组请建议我其他解决方案。谢谢。下面是我的代码，用于 3 个数组的笛卡尔积。

我有 n 个带有项目的 inputLists。现在我想计算包含原始 inputLists 中所有项目组合的 resultLists（长度为 n）（取每个 inputList 中的一项）。

我想我应该在这里提供一个例子（n = 3）：

我觉得有点愚蠢，但我不知道如何实现（C++）一个函数，为任何 n 和任何 inputList 长度创建这些结果。我想我应该使用某种递归，但我不知道如何。
有任何想法吗？

假设我们要给出一些项目的列表列表，比如字符串。

（真正的用例与字符串等无关，这只是一个模型）

我写了一个递归方法来做到这一点，但我对它不满意，因为它创建了很多被扔掉的临时集（是的，我知道在 java 中创建对象很便宜，通常 cpu 指令比 C 中的 malloc 少（源: Java Concurrency in Action, p241)，eden GC 很便宜，等等等等。幽默我 :)。

那么，你会怎么做呢？

编辑：要清楚，我不想创建排列。我想创建 sizeof(list of lists) 大的集合。

假设我有以下数据：

因此，每个产品都有一个或多个零件，每个零件都有一种或多种类型。

我想选择一个产品、它的零件和它的类型。假设我可能有数千个条目，所以通常我想在选择的同时进行过滤。这三个表通常会导致笛卡尔产品查询，鉴于这种情况，我需要运行一个查询，该查询相当于“给我按（部件为 Ink 的类型名称）排序的前 2 个产品，然后（类型名称在部分是烹饪）”

有没有人有任何想法？提前谢谢了

我正在使用笛卡尔积加入 2 个表，如下所示。

这当然会显示 2 列和各自的值。

但是，我随后想使用 COUNT/GROUP BY 和 SUM/GROUP BY 进一步操作数据，但无法找到任何可以使用 2 个表开始工作的相关示例。（把它们分开做是可以的，只是让它们一起工作才是问题所在）。

对于最终结果，我想显示 3 列显示 4 种类型的分组，每种类型下的条目数，以及每种类型的总金额/SUM，例如。

类型 - 类型计数 - 总值

一个 - 5 - 500

乙 - 6 - 1000

C - 1 - 50

D - 2 - 100

我有两张桌子，custassets和tags。为了生成一些测试数据，我想做INSERT INTO一个多对多表，其中 aSELECT从每个表中获取随机行（以便一个表中的随机主键与第二个表中的随机主键配对）。令我惊讶的是，这并不像我最初想象的那么容易，所以我坚持用它来自学。

这是我的第一次尝试。我选择 10custassets和 3 tags，但在每种情况下都相同。我会很好地修复第一个表，但我想随机分配分配的标签。

这会产生：

然后我尝试了以下方法：在列列表中进行第二次RANDOM()调用。SELECT然而这个更糟糕，因为它选择了一个标签 PK 并坚持下去。

结果：

这在脚本语言中很容易，而且我确信使用存储过程或临时表可以很容易地完成。但是我可以只用一个INSERT INTO SELECT吗？

我确实考虑过使用随机函数选择整数主键，但不幸的是，两个表的主键在增量序列中都有间隙（因此可能在每个表中选择一个空行）。不然就好了！

我有 6 个数组，每个数组有 8 个元素。我想编写一个方法来揭示所有数组的所有元素的所有可能组合，例如：

我怎样才能以最有效、对性能最友好的方式做到这一点？