问题标签 [combinations]

我想枚举A框中N个球的所有可能组合。

示例：我有8个球要处理3 个盒子：

我的第一个问题是我需要A循环来执行此操作，但我希望A和N成为用户的输入。那么如何在不编写用户可能需要的所有可能数量的循环的情况下呢？

a和N的值在 2 到 ~800 之间，因此对计算时间的要求很高。如何优化该算法？

如果您使用 python 语言回答我，我将不胜感激。感谢所有贡献！

给定一个按普遍使用顺序排序的常用词列表，是否有可能按照“最常用”序列的顺序形成任意长度（任何所需数量的词）的词组合。例如，如果最常见的词是“a, b, c”，那么对于长度为 2 的组合，将生成以下内容：

这是长度 3 的正确列表：

对于任意数量的元素的 2 或 3 个单词（设置长度）的组合，这很容易实现，但是可以对任意长度执行此操作吗？我想在 PHP 中实现它，但非常感谢伪代码甚至算法摘要！

我最近开始学习 python 并且有一个关于 for 循环的问题，我希望有人能回答。我希望能够打印从一到十的两个数字的所有可能产品。所以：2 x 2、2 x 3、2 x 4...2 x 10、3 x 2、3 x 3...3 x 10、4 x 2、4 x 3 等等...我本来以为最简单的方法是使用两个 for 循环，但我不确定。谁能告诉我这是怎么做到的。

这个问题与 KenKen 拉丁方谜题的那些部分有关，这些部分要求您找到 ncells 数字的所有可能组合，其值为 x 使得 1 <= x <= maxval 和 x(1) + ... + x(ncells) =目标总和。在测试了几个更有希望的答案之后，我将把答案奖授予 Lennart Regebro，因为：

1. 他的例行程序和我的一样快（+-5%），并且

2. 他指出我原来的例程在某个地方有一个错误，这让我看到了它真正想要做什么。谢谢，伦纳特。

chrispy 贡献了一个似乎与 Lennart 相当的算法，但 5 小时后，sooo，第一个得到它。

备注：Alex Martelli 的基本递归算法是一个示例，它制作了所有可能的组合并将它们全部扔到筛子上，看看哪个穿过了孔。这种方法比 Lennart 或我的方法花费的时间要长 20 倍以上。（将输入提升到 max_val = 100，n_cells = 5，target_sum = 250，在我的盒子上是 18 秒 vs. 8+ 分钟。） 道德：不生成所有可能的组合是好的。

另一句话：Lennart 和我的例程以相同的顺序生成相同的答案。它们实际上是从不同角度看到的相同算法吗？我不知道。

我发生了什么事。如果您对答案进行排序，例如，以 (8,8,2,1,1) 开头并以 (4,4,4,4,4) 结尾（max_val=8, n_cells=5, target_sum =20），该系列形成一种“最慢下降”，第一个是“热”，最后一个是“冷”，中间有尽可能多的阶段。这与“信息熵”有关吗？观察它的正确指标是什么？是否有一种算法可以按热量的降序（或升序）产生组合？（据我所见，这个没有，尽管它在很短的时间内很接近，看着标准化的标准开发。）

这是 Python 例程：

我有一个与此处回答的问题相似但不相同的问题。

我想要一个函数从 n 个元素的列表中生成所有元素的k组合。请注意，我正在寻找组合，而不是排列，并且我们需要一个用于改变k的解决方案（即，对循环进行硬编码是不行的）。

我正在寻找一种解决方案，a) 优雅，b) 可以在 VB10/.Net 4.0 中编码。

这意味着 a) 需要 LINQ 的解决方案是可以的，b) 那些使用 C#“yield”命令的解决方案不是。

组合的顺序并不重要（即，字典顺序、格雷码、你有什么），如果两者发生冲突，优雅比性能更受青睐。

（这里的 OCaml 和 C# 解决方案将是完美的，如果它们可以在 VB10 中编码。）

我被要求编写一个例程来确定产品配置器中可能组合的数量。

配置器非常简单。尽管它具有比这更多的功能，但它可以建模为几个“无线电组”（如 UI 控件），其中必须选择 n 个选项之一。

唯一可以使用的约束是规则，如果选择了一个选项，则不能选择另一个选项。

所以我想做的是计算可以配置的不同产品的数量，给定一组选项组和约束。

我采用了一种天真的方法来解决这个问题，使用包含-排除原则。但是据我所知，任何基于此方法的算法都应该在 O(2^n) 中运行，这将不起作用。当然，有几种可能的优化应该可以提供不错的运行时间，但仍然存在很容易构建的最坏情况。

这就是我现在所处的位置。有什么建议么？

更新

我意识到我还没有解释规则如何应用得足够好。

有几个组有选项。每个组中必须选择一个且只有一个选项。一个组中可以有一个或多个选项。

只有一种类型的约束。如果选择了某个组中的选项A，则无法选择其他组中的选项B。可以有任意数量的约束，没有限制有多少约束/规则适用于选项组或选项本身。

所以一个例子是：

第一组：
x1 x2 x3 x4 x5

第 2 组：
y1 y2 y3

第 3 组：
z1 z2 z3 z4

约束：
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

*如果在 group1 中选择了 option x1，则不能选择 group 2 中的 option y2。

使用包含-排除，我将计算组合数为

组合 = C_无规则- C _r[1] - C _r [2] - C _r [3] + C _r [1,2] + C _r [1,3] + C _r [2,3] - C _r [1, 2,3]

在哪里

C_无规则= 5 * 3 * 4

C _r [a,b,c] = 违反规则 a、b 和 c 的组合数。

不幸的是，该方法需要 2^|rules| 计算。

关于 F# 中元素组合的最优雅和最简单实现的另一个问题。

它应该返回输入元素的所有组合（列表或序列）。第一个参数是组合中元素的数量。

例如：

我正在寻找一种算法，该算法将计算一个n-bit单词中二进制位模式的数量，这些位模式等于或小于小于的任意限制2^n。此外，我想为所有1-bit组合、2-bit组合等生成计数。显然，如果限制是2^n，就会有2^n组合(C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on)。但是，如果施加限制，则并非所有可能的组合都是有效的（小于施加的限制）。

例如，说n=4。有 16 种可能的位模式，其中 15 种包含 1 或更多1-bits。如果限制为 10，则大于 10 的模式将不包括在计数中。因此，对于单个位模式，有效的将是0001、0010、0100和1000。两位模式将是0011, 0101, 0110, 1001. 模式1010并且1100不会被计算在内，因为它们超过了 10。唯一的 3 位位将是0111，而唯一的 4 位模式1111超过了限制。

如果F是我的计数函数，F(4,10,1)将返回 4，4-bit小于 10 的 1 位模式的数量。F(4,10,2)将返回 4，其中为C(4,2)6。因为 的实际值n可能很大（40 或位），枚举可能的模式，针对限制进行测试并计算有效的是不切实际的。

关于如何有效地做到这一点的任何想法？

假设有n个条目，每个条目都可以取0或1的值。这意味着这些条目有2^n种可能的组合。条目的数量可以从1到6不等。

如何在不使用一千个 IF 的情况下将每个可能的组合创建为一个数字序列（即n = 2: 00, 01, 10, 11）？

我有两个数组：

我希望返回所有可能的组合，例如：

空值应该被忽略。