问题标签 [combinations]

假设您有货物。它需要从 A 点到 B 点，从 B 点到 C 点，最后从 C 点到 D 点。您需要用最少的钱在五天内到达那里。每条支线有三个可能的托运人，每条支线都有自己不同的时间和成本：

您将如何以编程方式寻找最佳组合？

到目前为止，我最好的尝试（第三或第四种算法）是：

1. 为每条腿找到最长的托运人
2. 淘汰最“贵”的一个
3. 为每条腿找到最便宜的托运人
4. 计算总成本和天数
5. 如果天数可以接受，则完成，否则，转到 1

在 PHP 中快速模拟（请注意，下面的测试数组可以流畅地工作，但是如果您使用上面的测试数组尝试它，它不会找到正确的组合）：

我想我实际上可能需要做一些事情，我逐个制作每个组合（带有一系列循环）并将每个组合的总“分数”相加，然后找到最好的一个......

编辑：澄清一下，这不是“家庭作业”（我不在学校）。这是我当前工作项目的一部分。

要求（一如既往）一直在不断变化。如果在我开始解决这个问题时给了我当前的限制，我将使用 A* 算法的一些变体（或 Dijkstra 或最短路径或单纯形或其他东西）。但是一切都在变化和变化，这将我带到了现在的位置。

所以我想这意味着我需要忘记我到目前为止所做的所有废话，只使用我知道我应该使用的东西，这是一种寻路算法。

我正在尝试编写一段代码来执行以下操作：

取数字 0 到 9 并为该数字分配一个或多个字母。例如：

当我有像 0123 这样的代码时，对它进行编码就很容易了。它显然会构成代码 NLTD。当引入像 5,6 或 8 这样的数字时，情况会有所不同。像 051 这样的数字会导致不止一种可能性：

NVL 和 NFL

很明显，对于较长的数字，包括 5,6 或 8 之类的几个数字，这会变得“更糟”。

由于数学很差，我还没有想出一个像样的解决方案，让我可以给程序输入一堆数字并让它吐出所有可能的字母组合。所以我很想得到一些帮助，因为我似乎无法弄清楚。挖掘了一些关于排列和组合的信息，但没有运气。

感谢您的任何建议/线索。我需要编写代码的语言是 PHP，但任何一般性提示都将受到高度赞赏。

更新：

更多背景信息：（非常感谢您的快速回复！）

我的问题背后的想法是构建一个脚本，帮助人们轻松地将他们想要记住的数字转换为更容易记住的单词。这有时被称为“伪命理”。

我希望脚本为我提供所有可能的组合，然后将这些组合保存在剥离单词的数据库中。这些被删除的单词只是来自字典，并且我在问题中提到的所有字母都被删除了。这样，要编码的数字通常可以很容易地与一个或多个数据库记录相关联。当这种情况发生时，你最终会得到一个单词列表，你可以用它来记住你想记住的数字。

我想编写一个函数，它将一组字母作为参数，并选择其中的一些字母。

假设您提供了一个包含 8 个字母的数组，并希望从中选择 3 个字母。那么你应该得到：

数组（或单词）作为回报，每个包含 3 个字母。

我有 4 个二进制位

通常答案很简单：2^4，或 16 种不同的组合；它看起来像下面这样：

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

但是，LSB（位 0）每次迭代都会改变状态。

我需要一种算法，其中位的状态在所有迭代中只改变一次；即，我需要我所有的位都像 MSB（位 3）一样工作。

我怎样才能做到这一点？

编辑

似乎大多数人都认为只有 5 种可能的解决方案。然而，这假设有一个值的起点和一个终点。这没关系，所以我将给出一个真实世界的场景来更好地解释。

假设我有一个数字闹钟，可以提供 4 个输出。每个输出都可以被编程为在某个时间打开和在某个时间关闭，并且可以彼此独立地进行编程，例如。我可以将输出 1 编程为在凌晨 1 点打开并在凌晨 3 点关闭，而我可以将输出 2 编程为在下午 7 点打开并在凌晨 2 点关闭。每个输出可以保持多长时间没有限制。

现在我想把这个闹钟挂在电脑上，尽可能接近当前的正确时间。例如，如果时钟显示时间是下午 2:15，我的电脑就知道闹钟在下午 12 点到下午 6 点的范围内。我希望能够获得尽可能小的范围。我能得到的最小范围是多少？

我有一个包含 15 个数字的列表，我需要编写一些代码来生成这些数字的所有 32,768 个组合。

我发现一些代码（通过谷歌搜索）显然可以满足我的要求，但我发现代码相当不透明并且对使用它持谨慎态度。另外，我觉得必须有一个更优雅的解决方案。

我唯一想到的就是循环遍历十进制整数 1-32768 并将它们转换为二进制，然后使用二进制表示作为过滤器来挑选出适当的数字。

有人知道更好的方法吗？使用map()，也许？

问题

我需要创建 32 位数字（有符号或无符号都无关紧要，无论如何都不会设置最高位）并且每个数字都必须设置给定数量的位。

天真的解决方案

最简单的解决方案当然是从零开始。在一个循环内，数字现在增加一，对位的数量进行计数，如果计数具有所需的值，则将数字存储到列表中，如果不是，则循环重复。如果找到足够的数字，则停止循环。当然，这工作得很好，但是一旦所需的位数变得非常高，它就会非常慢。

更好的解决方案

设置（假设）5 位的最简单数字是设置前 5 位的数字。这个号码可以很容易地创建。在一个循环中，第一位被设置并且数字向左移动一个。这个循环运行了 5 次，我找到了第一个设置了 5 位的数字。接下来的几个数字也很容易创建。我们现在假设这个数字是 6 位宽，并且最高的没有设置。现在我们开始将第一个零位向右移动，因此我们得到 101111、110111、111011、111101、111110。我们可以通过在前面添加另一个 0 并重复此过程来重复此过程。0111110、1011110、1101110 等。然而，这样数字的增长速度会比必要的快得多，因为使用这种简单的方法，我们会忽略像 1010111 这样的数字。

那么有没有更好的方法来创建所有可能的排列，一种通用的方法，可以使用，不管下一个数字有多少位，也不管我们需要设置多少位？

我正在寻找一种方法来生成按单个属性排序的对象组合。我不认为字典顺序是我正在寻找的......我会尝试举一个例子。假设我有一个对象 A、B、C、D 的列表，其中我想要按 3、3、2、1 排序的属性值。这给出了 A3、B3、C2、D1 对象。现在我想生成 2 个对象的组合，但它们需要按降序排列：

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

生成所有组合并对它们进行排序是不可接受的，因为现实世界的场景涉及大集合和数百万个组合。（40 个，8 个订单），我只需要高于特定阈值的组合。

实际上，我需要按给定属性的总和分组的阈值以上的组合计数，但我认为这样做要困难得多 - 所以我会满足于开发高于阈值的所有组合并计算它们。如果有可能的话。

编辑 - 我最初的问题不是很精确......我实际上并不需要订购这些组合，只是认为它有助于隔离高于阈值的组合。更准确地说，在上面的例子中，给定阈值 5，我正在寻找一个信息，即给定集合产生 1 个总和为 6 ( A3 B3 ) 和 2 总和为 5 ( A3 C2, B3 C2)。我实际上并不需要组合本身。

我正在研究子集和问题，但如果我正确理解给定的动态解决方案，它只会给你信息是否有给定的总和，而不是总和的计数。

谢谢

我有一个这种类型的列表 List> 包含这个

我想要这样的所有组合

等等。

根据您的说法，这可以使用 Linq 解决吗？

我有一个显示两个对象的页面，然后用户选择其中一个。我将偏好和组合记录在 MSSQL 数据库中，并最终存储如下数据：

现在我想避免再次显示对象（1,2 / 2,1）的组合。

那么如何生成随机组合以向用户显示不包括先前查看的组合？

这似乎应该是一个非常直截了当的问题，但像大多数程序员一样，我缺乏睡眠和咖啡，因此非常感谢您的帮助 :-)

非常天真的方法是这样的（并且对这个函数的所有调用都必须包含在一个检查中，以查看用户是否已经对 nCr 进行了多次评分，其中 n 是项目数，r 是 2）：

编辑

使用一些 SQL，我可以生成所有不完整项目的列表（即，有一个涉及用户未见过的项目的组合），但我认为这不是特别有用。

我还可以想象在选择 2 个随机项目之前生成所有可能的组合并消除已经查看过的组合，但这是另一个糟糕的解决方案。

一种可能性（大 n 的内存密集型）是生成所有可能的组合并将组合 ID 存储在评级中。然后我可以对所有组合进行 SELECT WHERE combinationId IS NOT IN (SELECT combinationId FROM rating WHERE userId=x) 并进行一些更改以反映组合的对称关系。

我有一个项目清单，每个项目都有一个数量。

或者，这可以被视为：

您将如何获取这些项目的每个组合的列表，请记住顺序完全不重要（因此[1,2,3] == [3,2,1]），并且并非每个项目都必须存在于结果中。

我想输出可能如下所示：

或者，甚至更好：