问题标签 [combinatorics]

给定一个种子字符串，我想找到它的邻居最多在 2 个位置上不同。生成字符串所涉及的所有数字只有四个（即0、1、2、3）。这是我的意思的例子：

但是为什么我的这段代码无法正确生成呢？特别是当种子字符串不是“000”时。

其他方法也受到欢迎，尤其是速度改进。因为我们将处理数百万个长度为 34 到 36 的种子标签。

给定一个包含重复元素的集合** S，如何确定 S 的所有可能子集的总数，其中每个子集都是唯一的。

例如，假设 S = {A, B, B} 并设 K 为所有子集的集合，则 K = {{}, {A}, {B}, {A, B}, {B, B}, {A, B, B}} 因此 |K| = 6。

另一个例子是如果 S = {A, A, B, B}，那么 K = {{}, {A}, {B}, {A, B}, {A, A}, {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} 和因此 |K| = 9

很容易看出，如果 S 是一个只有唯一元素的实集，那么 |K| = 2^|S|。

计算这个值的公式是什么|K| 给定一个“集合”S（有重复项），而不生成所有子集？

** 从技术上讲不是一套。

这与问题如何在 Python 中生成列表的所有排列有关

如何生成符合以下条件的所有排列：如果两个排列彼此相反（即 [1,2,3,4] 和 [4,3,2,1]），它们被认为是相等的，并且只有其中一个应该是最终结果。

例子：

我正在排列包含唯一整数的列表。

结果排列的数量会很高，所以如果可能的话，我想使用 Python 的生成器。

编辑：如果可能的话，我不想将所有排列的列表存储到内存中。

给定一个场景，我们有多个项目对列表，例如：

1. {12,13,14,23,24}
2. {14,15,25}
3. {16,17,25,26,36}

其中 12 是一对项目“1”和“2”（因此 21 相当于 12），我们想要计算可以从每个列表中选择项目对的方式的数量，使得没有单个项目是重复。您必须从每个列表中选择一个，并且只选择一对。每个列表中的项目数和列表数是任意的，但您可以假设至少有两个列表，每个列表至少有一对项目。并且这些对是由有限字母表中的符号组成的，假设为数字 [1-9]。此外，列表既不能包含重复对 {12,12} 或 {12,21}，也不能包含对称对 {11}。

更具体地说，在上面的示例中，如果我们从第一个列表中选择项目对 14，那么我们对第二个列表的唯一选择是 25，因为 14 和 15 包含“1”。因此，第三个列表中的唯一选择是 36，因为 16 和 17 包含“1”，而 25 和 26 包含“2”。

有没有人知道一种有效的方法来计算项目对的总组合，而无需遍历选择的每一个排列并询问“这是一个有效的选择吗？”，因为每个列表都可以包含数百对项目？

更新

在花了一些时间之后，我意识到当没有一个列表共享一个不同的对时，计算组合的数量是微不足道的。但是，只要在两个或多个列表之间共享不同的对，组合公式就不再适用。

截至目前，我一直在试图弄清楚是否有一种方法（使用组合数学而不是蛮力）来计算每个列表具有相同项目对的组合数量。例如：

1. {12,23,34,45,67}
2. {12,23,34,45,67}
3. {12,23,34,45,67}

我有一个包含 2000 万用户和这些人之间联系的数据库。如何在编程 中以最有效的方式证明“六度分离”的概念？

链接到关于六度分离的文章

• 我编辑了原始文本以节省潜在读者的时间和健康。也许有人会真正使用它。

我知道这是基本的东西。可能非常非常基本。
如何获得给定集合的所有可能组合。例如
字符串集=“abc”；
我希望得到：
abc aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
并且列表还在继续（如果没有设置长度限制）。

我正在为此寻找一个非常干净的代码 - 我发现的所有代码都很脏并且无法正常工作。我可以对我编写的代码说同样的话。

我需要这样的代码，因为我正在编写在多个线程上工作的蛮力（md5）实现。模式是有父进程为线程提供它们自己的组合块，所以它们可以自己处理这些。
示例：第一个线程获得 100 个排列的包，第二个获得下一个 100 个等。
让我知道是否应该在任何地方发布最终程序。

编辑#2 再次感谢你们。
多亏了你，我已经完成了用 MPICH2 实现的 Slave/Master Brute-Force 应用程序（是的，可以在 linux 和 windows 下工作，例如网络），因为这一天快结束了，我已经浪费了很多时间（和太阳）我将继续我的下一个任务...... :)
你向我展示了 StackOverflow 社区很棒 - 谢谢！

我正在处理每个元素与其原始位置不同的排列。我想要一个给定{输入长度，行和数字}的算法，会给我输出数字。这是一个例子：

如果输入长度为四，则 0123 的所有排列为：

没有数字在同一位置的排列（每个数字都移动了）：

编号从 0 开始，因此如果函数的输入是 {4,0,0}，则输出应该是第 0（第一个）排列的第 0（最左边）数字。1032的第一位是1。

如果输入是 {4,1,1}，则输出是 1230 的第二个数字，即 2。

行数可能大于排列数。在这种情况下，取余数模排列数（在上述情况下，行模 9）。

在c语言中会很棒。

（这不是家庭作业，是为了工作。Cuckoo hashing 如果你必须知道的话。我想随机选择我将在每个阶段进行的交换，看看当表数大于两个时它是否比 BFS 更好.)

我正在寻找以下一类问题的名称，以便我可以通过谷歌搜索有效的算法和更多信息。

我有一个包含三个字符 {-1, 0, 1} 的字母表。

我需要有效地生成所有长度为 24 的字符串，这些字符串主要是 {0}，但有零到八个 {1,-1} 字符以某些模式分布。（模式涉及对 {-1} 的数量和配对的限制）。符合我标准的字符串总数非常少：大约 128,000。

那么这类问题/算法的名称是什么？

尝试学习一些 Scala 并遇到了这个问题。我在这里找到了所有组合的解决方案，没有重复，我有点理解它背后的想法，但有些语法让我很困惑。我也不认为该解决方案适用于重复的情况。我想知道是否有人可以提出一些我可以使用的代码。我有很多关于组合学的材料，并且了解问题和迭代解决方案，我只是在寻找 scala-y 的方法。

谢谢

我们有一组彼此非常接近的无线电节点，并希望为它们分配频率以尽量减少重叠。为了完全覆盖该地区，无线电频道需要超额订阅，因此我们将让附近的无线电以相同的频率传输。

样本数据：
5 频率
343 无线电
4158 边缘

我目前最好的猜测是随机生成一组频率分配并在无线电之间交换频率，直到 10 代后最好的分数没有提高。分数是相同频率的无线电的 1/range^2 的总和。

每个边缘都是无线电之间的距离，已针对墙壁和地板进行了校正。超过 2* 最大无线电范围的边缘已从列表中剔除。

有没有更好的办法？