问题标签 [combinatorics]

我决定学习并发性，并想了解来自两个不同进程的指令有多少种重叠方式。这两个过程的代码只是一个 10 次迭代循环，每次迭代执行 3 条指令。我发现问题在于将 X 指令固定在一个点上，然后在空间之间拟合来自其他进程的其他 X 指令，同时考虑到它们必须是有序的（进程 B 的指令 4 必须始终位于指令 20 之前）。

我编写了一个程序来计算这个数字，查看结果我发现解决方案是 n 组合 k，其中 k 是在一个进程的整个循环中执行的指令数，因此对于 10 次迭代，它将是 30，并且n 为 k*2（2 个进程）。换句话说，n 个对象的 n/2 是固定的，并且必须在空间中适合 n/2，而后者的 n/2 不会失去它们的顺序。

好的问题解决了。不，不是。我不知道为什么会这样，我知道组合的定义是，您可以通过多少种方式从一组 n 中获取 k 个元素，使得所有组都不同，但您获取元素的顺序却没有没关系。在这种情况下，我们有 n 个元素，实际上我们将它们全部取走，因为所有指令都已执行 (n C n)。

如果说一个包里有 2k 个蓝色 (A) 和红色 (B) 对象来解释它，并且您从包中取出 k 个对象，那么当实际执行 2k 条指令时，您仍然只取了 k 条指令。你能解释一下吗？

提前致谢。

我的代码有一个名为 INPUTS 的列表，其中包含动态数量的列表，我们称它们为 A、B、C、..N。这些列表包含动态数量的事件

我想用每个事件组合调用一个函数。用一个例子来说明：

我需要为每个组合多次调用我的函数（输入计数是动态的，在这个例子中它是三个参数，但它可以或多或少）

这是我到目前为止所想到的：到目前为止，我的方法是建立一个组合列表。元素组合本身就是输入数组 A、B 和 C 的“索引”列表。对于我们的示例：

我的列表 iCOMBINATIONS 包含以下 iCOMBO 列表

然后我会这样做：

但是我需要找到一种方法来为任何给定数量的 INPUTS 及其事件构建列表 iCOMBINATIONS。有任何想法吗？

实际上有比这更好的算法吗？任何可以帮助我的伪代码都会很棒。

C#（或 VB）

谢谢你

我正在阅读自己（不是为硬件）关于编程的内容，其中一个练习涉及在 R 中编程 Pascal 的三角形。我的第一个想法是制作一个列表，然后将内容附加到它上面，但效果不太好。然后我想从一个向量开始，然后在最后列出一个列表。然后我想到了制作一个矩阵，并在最后列出一个列表。

甚至不知道用哪种方法来解决这个问题。

有什么提示吗？

谢谢

这不是家庭作业。

我看到这篇文章赞扬了 Linq 库以及它在做组合数学方面的出色表现，我心想：Python 可以以更易读的方式来做这件事。

在使用 Python 半小时后，我失败了。请完成我离开的地方。另外，请以最Pythonic和最有效的方式进行。

谢谢！

This is a question on combinatorics from a non-mathematician, so please try to bear with me!

Given an array of n distinct characters, I want to generate subsets of k characters in a minimal-change order, i.e. an order in which generation i+1 contains exactly one character that was not in generation i. That's not too hard in itself. However, I also want to maximise the number of cases in which the character that is swapped out in generation i+1 is the same character that was swapped in in generation i. To illustrate, for n=7, k=3:

abc abd abe* abf* abg* afg aeg* adg* acg* acd ace* acf* aef adf* ade bde bdf bef bcf* bce bcd* bcg* bdg beg* bfg* cfg ceg* cdg* cde cdf* cef def deg dfg efg

The asterisked strings indicate the case I want to maximise; e.g. the e that is new in generation 3, abe, replaces a d that was new in generation 2, abd. It doesn't seem possible to have this happen in every generation, but I want it to happen as often as possible.

Typical array sizes that I use are 20-30 and subset sizes around 5-8.

I'm using an odd language, Icon (or actually its derivative Unicon), so I don't expect anyone to post code that I can used directly. But I will be grateful for answers or hints in pseudo-code, and will do my best to translate C etc. Also, I have noticed that problems of this kind are often discussed in terms of arrays of integers, and I can certainly apply solutions posted in such terms to my own problem.

Thanks

Kim Bastin

Edit 15 June 2010:

I do seem to have got into deeper water than I thought, and while I'm grateful for all answers, not all of them have been relevant. As an example of a solution which is NOT adequate, let me post my own Unicon procedure for generating k-ary subsets of a character set s in a minimal change order. Things you need to know to understand the code are: a preposed * means the size of a structure, so if s is a string, *s means the size of s (the number of characters it contains). || is a string concatenation operation. A preposed ! produces each element of a structure, e.g. each character of a string, in turn on successive passes. And the 'suspend' control structure returns a result from a procedure, but leaves the procedure 'in suspense', with all local variables in place, so that new results can be produced if the procedure is called in a loop.

Note that the output of the above procedure is not optimal in my sense. One result of my investigations so far is that the maximum 'swapping score' for a list of k-ary subsets of n elements is not less than comb(n-1, k), or in the case of n=7, k=3, the maximum score is at least comb(6, 3) = 20. I define the 'swapping score' of a list as the number of items in the list whose new element replaces an element in the previous item which was itself new. I haven't got the mathematical equipment to prove this, but it is easy to see with k=1 or k=2. For certain (n,k) a slightly higher score is possible, as in the case of n=7, k=3:

abc abd abe abf abg
acg adg aeg afg
efg dfg cfg bfg
beg bdg bcg
bcd bce bcf
bdf bef
def cef aef
adf acf
acd ace
ade
bde cde
cdf cdg
ceg
deg (swapping score = 21)

It may be noted that the above list is in 'strong minimal change order' (like word golf: the new character is always in the same position as the character it replaces), which may indicate the direction my own work is taking. I hope to post something more in a few days.

Kim

编辑：请参阅以编程方式解决“谁拥有斑马”？对于类似的问题

LSAT 中有一类逻辑问题是这样的：

广播的七个连续时间段（按时间顺序 I 到 7 编号）将被六首歌曲磁带（G、H、L、O、P、S）和恰好一个新闻磁带填满。每个磁带被分配到不同的时隙，并且没有磁带比任何其他磁带长。广播受以下限制：
L 必须在 O 之前立即播放。
新闻磁带必须在 L 之后的某个时间播放
。G 和 P 之间必须恰好有两个时隙，无论 G 是否在 P 之前或是否G 在 P 之后。

我有兴趣生成一个满足条件的排列列表作为学习测试和编程挑战的一种方式。但是，我不确定这是哪一类排列问题。我将类型问题概括如下：

给定一个长度为 n 的数组 A：

1. 在 A 中，一组 n 个独特的项目有多少种排列方式？例如。有多少种方法可以重新排列 ABCDEFG？
2. 如果唯一项目集合的长度小于 A 的长度，如果集合中的项目可能出现不止一次，那么集合在 A 中的排列方式有多少？例如。ABCDEF => AABCDEF; ABBCDEF 等
3. 如果集合中的项目受到“阻塞条件”的约束，那么在 A 内可以排列一组唯一项目的方式有多少？

我的想法是对限制进行编码，然后使用 Python 的 itertools 之类的东西来生成排列。欢迎提出想法和建议。

我正在尝试编写一个脚本，该脚本将采用一个项目字典，每个项目包含 0 到 10 的值的属性，并添加各种元素以选择哪些项目组合达到所需的总数。我还需要脚本来执行此操作，仅使用具有相同“插槽”的项目。

例如：

然后，脚本需要从“item_list”dict 中选择每个“slot”使用 1 个项目的组合，以便在添加时达到预期的结果。

例如，如果期望的结果是：'prop_a': 3, 'prop_b': 3, 'prop_c': 8, 'prop_d': 0, 脚本会选择 'item_2', 'item_6' 和 'item_9',以及任何其他有效的组合。

任何想法如何做到这一点？它不需要在 python 中，甚至不需要一个完整的脚本，但对我来说，理论上如何做到这一点的解释就足够了。我已经尝试过遍历每个组合，但这似乎很快就让我们掌握了并且无法管理。实际脚本将需要使用 20 个不同的“插槽”对大约 1,000 个项目执行此操作，每个“插槽”具有 8 个属性。

谢谢您的帮助！

我想要一种非递归方法来解决生成某些字符或数字组合的问题。

因此，给定数字 n 的子集 k，生成所有可能的组合 n!/k!(nk)!

给定前一个组合，递归方法将给出一个组合。

非递归方法将生成循环索引i的给定值的组合。

我用这段代码解决了这个问题：

用 n = 4 和 k = 3 测试，它可以工作，但如果我将 k 更改为 > 3 的数字，它就不起作用。

是不是因为 (nk)! 如果 n = 4 且 k = 3 为 1。如果 k > 3 它会大于 1？

谢谢。

我有 n 个扇区，逆时针枚举 0 到 n-1。这些扇区之间的边界是无限的分支（其中 n 个）。扇区位于复平面中，对于 n 偶数，扇区 0 和 n/2 被实轴二等分，扇区间距均匀。

这些分支在某些点相遇，称为交汇点。每个路口都与扇区的一个子集（至少其中 3 个）相邻。

指定连接点（以前缀顺序，假设从与扇区 0 和 1 相邻的连接点开始）以及连接点之间的距离，唯一地描述了树。

现在，给定这样的表示，我如何查看它是否与实轴对称？

例如，n=6，树 (0,1,5)(1,2,4,5)(2,3,4) 在实线上有三个交汇点，所以它是关于实轴对称的。如果 (015) 和 (1245) 之间的距离等于从 (1245) 到 (234) 的距离，这也是关于虚轴对称的。

树 (0,1,5)(1,2,5)(2,4,5)(2,3,4) 有 4 个连接点，无论是虚轴还是实轴，这都不是对称的，但它有 180 个如果表示中的前两个和最后两个交汇点之间的距离相等，则旋转对称度数。

编辑：这里是所有有 6 个分支的树，距离为 1。 http://www2.math.su.se/~per/files/allTrees.pdf

因此，鉴于描述/表示，我想找到一些算法来确定它是否是对称的实数、虚数和 180 度旋转。最后一个示例具有 180 度对称性。

编辑2：这实际上是为了我的研究。我也在 mathoverflow 上发布了这个问题，但是我在竞赛编程中的日子告诉我，这更像是一个 IOI 任务。mathematica 中的代码会非常好，但 java、python 或任何其他人类可读的语言就足够了。

（这些对称性对应于薛定谔方程中的特殊势能，它在量子力学中具有很好的性质。）

我有一组项目，例如：{1,1,1,2,2,3,3,3}，还有一组限制性的集合，例如 {{3},{1,2},{1 ,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}。我正在寻找项目的排列，但第一个元素必须是 3，第二个元素必须是 1 或 2，等等。

一种适合的排列是：{3,1,1,1,2,2,3}

一般来说，是否有一种算法可以计算这个问题的所有排列？这类问题有名称吗？

为了说明，我知道如何为某些类型的“限制集”解决这个问题。项目集：{1,1,2,2,3}，限制条件 {{1,2},{1,2,3},{1,2,3},{1,2},{1,2 }}。这等于 2!/(2-1)!/1! * 4!/2!/2!。首先有效地排列 3，因为它是最严格的，然后在有空间的地方排列剩余的项目。

还有……多项式时间。那可能吗？

更新：这将在下面的链接中进一步讨论。上面的问题称为“计算完美匹配”，上面的每个排列限制都由插槽矩阵上的 {0,1} 表示。

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots