寻找一个有限制条件的排列集合

Question

寻找一个有限制条件的排列集合

8

我有一组N^2个数字和N个箱子。每个箱子应该分配N个数字。我面临的问题是找到一组分布，将数字映射到箱子，满足约束条件：每对数字只能共享一个箱子一次。

分布可以用NxN矩阵很好地表示，其中每行代表一个箱子。然后问题就是找到矩阵元素的一组排列，其中每对数字只共享一行一次。无论是哪一行都不重要，只要两个数字都被分配到同一个箱子里。

以下是满足N=8约束条件的3个排列示例：

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

 0  8 16 24 32 40 48 56
 1  9 17 25 33 41 49 57
 2 10 18 26 34 42 50 58
 3 11 19 27 35 43 51 59
 4 12 20 28 36 44 52 60
 5 13 21 29 37 45 53 61
 6 14 22 30 38 46 54 62
 7 15 23 31 39 47 55 63

 0  9 18 27 36 45 54 63
 1 10 19 28 37 46 55 56
 2 11 20 29 38 47 48 57
 3 12 21 30 39 40 49 58
 4 13 22 31 32 41 50 59
 5 14 23 24 33 42 51 60
 6 15 16 25 34 43 52 61
 7  8 17 26 35 44 53 62

不属于上述集合的排列：

0 10 20 30 32 42 52 62
1 11 21 31 33 43 53 63
2 12 22 24 34 44 54 56
3 13 23 25 35 45 55 57
4 14 16 26 36 46 48 58
5 15 17 27 37 47 49 59
6 8 18 28 38 40 50 60
7 9 19 29 39 41 51 61

由于第二个排列与第一个排列发生了多次冲突，例如它们在一行中都配对了数字0和32。

枚举三个是容易的，它包括一个任意排列、它的置换和一个矩阵，其中行由前一个矩阵的对角线组成。

我找不到产生更多集合的方法。这似乎是一个非常复杂的问题，或者是一个简单的问题，有一个不明显的解决方案。无论哪种情况，如果有人有任何想法如何在合理的时间内解决N=8情况，或者确定问题的正确学术名称，那么我将不胜感激。

如果你想知道它有什么用处，我正在寻找一个调度算法，用于具有8个缓冲区的交叉开关，它将流量传输到64个目的地。调度算法的这一部分与输入流量无关，并且在一些硬连线的目的地缓冲区映射之间循环切换。目标是使每对目标地址仅在循环期内竞争同一个缓冲区一次，并最大化该周期的长度。换句话说，每对地址尽可能少地竞争同一个缓冲区。

编辑：

以下是我拥有的一些代码。 CODE

它是贪心的，通常在找到第三个排列后终止。但至少存在一组N个排列满足问题。

另一种选择需要涉及选择排列I并查找排列(I+1..N)，以检查排列I是否是由最大数量的排列组成的解的一部分。这将需要枚举所有排列来检查每个步骤，这是不可行的。

- user161111

整个问题有点啰嗦。"pair"是什么意思不太清楚。你所说的“每对数字只能共享同一个箱子一次”的限制是什么意思？ - Alex

我对你的限制“每一对数字只能在同一个箱子中出现一次”感到困惑。这不是N^2个独特数字的任何排列都显而易见的吗？你能展示一个违反这个限制的排列吗？ - Jim Lewis

约束条件需要满足整个排列集。因此，如果一个排列将数字1和2放在同一行上，则不允许集合中的其他排列再将1和2放在同一行上。 - user161111

正式地，设P(a,b,i)为谓词“a和b在排列i的同一行中出现”，假设有n个排列。那么约束条件是“不存在a、b <= N^2和i、j <= n，使得P(a,b,i) && P(a,b,j)”。 - Steve Jessop

P(a,b,i) 可以表示为 "R(a,i) == R(b,i)"，其中 R 是将二元组 (a,i) 映射到排列 i 中项 a 出现的行号的函数。 - Steve Jessop

如果你早上还喜欢你的代码 :-)，请将其作为答案发布，以便我们可以给你更多的赞！这是一个非常有趣的问题！ - Jim Lewis

4个回答

4

你需要的是组合设计块。使用链接页面上的命名法，您需要大小为(n^2，n，1)的设计，以获得最大k。按照您的命名法，这将给您n(n+1)个排列。从计数论的角度来看，这是理论上可能的最大值（请参见文章中关于b如何从v、k和lambda导出的解释）。对于某些质数p和整数k，使用仿射平面可以构造这样的设计，当且仅当n = p^k时存在。据推测，唯一存在的仿射平面就是这个大小。因此，如果您可以选择n，也许这个答案就足够了。

然而，如果您只是想找到一个大量的排列（对于给定的n^2），而不是最大理论可能的数量，我不确定这些对象的研究称为什么。

- Martin Hock

非常感谢！在块设计的维基百科页面上，我找到了一个链接，里面包含了我感兴趣的(64, 8, 1)解决方案的数据库。 - user161111

1

也许你可以将问题转化为图论问题。例如，你可以从具有 N×N 个顶点的完全图开始。在每一步中，你将图分成 N 个 N-团，并删除所有使用过的边。

对于 N=8 的情况，K64 具有 64×63/2 = 2016 条边，而六十四个 K8 团共有 1792 条边，因此你的问题可能不是不可能的 :-)

- John Fouhy

听起来很正确！而且很有见地——因为在一般情况下，找到团伙问题被认为是NP完全的。我怀疑的是，在最初的几次迭代中（当NxN图仍然相对密集时），可能很容易通过蛮力法找到，但随着边的删除，寻找团伙需要越来越长的时间。 - Jim Lewis

寻找最大团是NP完全问题。我不确定这个问题。如果存在，我认为团会很容易找到，因为每个顶点都必须是其中一个成员，并且您只对大小N感兴趣。问题在于贪心算法可能会选择错误的团，并且无法找到所有N，假设N存在（好吧，这是我的直觉）。 - John Fouhy

是的，基本上我实现的是找到所有的8-团。这很快速，有2个起始排列（找到了40320个8-团），只有1个起始排列也可以做到（找到了1600万个8-团）。但问题在于：

枚举所有合法的排列，即8个8-团的集合，需要处理40320^8或（1600万）^8个事务。
下一步中8-团和可能的排列数量取决于此步骤中排列的选择，贪婪算法确实行不通。完整的搜索需要在寻找排列I时评估所有后续排列（I+1..N）:/

- user161111

0

没错，贪心算法不起作用，因为你会用完数字。

很容易看出，在违反约束之前最多只能有63个排列。在第64个排列中，你必须将至少一个数字与已经配对的另一个数字配对。这就是鸽笼原理。

实际上，如果你使用我之前建议的禁止配对表，你会发现在用完之前最多只有N+1=9个排列。该表具有N^2 x (N^2-1)/2 = 2016个非冗余约束条件，每个新排列将创建N x (N choose 2) = 28个新配对。因此，在2016/28 = 9个排列后，所有配对都将被用完。似乎意识到排列如此之少是解决问题的关键。

你可以生成一个编号为n = 0 ... N-1的N个排列列表，如下所示：

A_ij = (i * N + j + j * n * N) mod N^2

通过在每个排列中移动列，生成新的排列。第n个排列的顶行是第n-1个排列的对角线。编辑：哎呀...这似乎只在N为质数时有效。

这会漏掉最后一个排列，你可以通过转置矩阵来得到：

A_ij = j * N + i

- Brian

通过检查给定值（例如1）的N-1个邻居，您还可以获得N+1的上限。在具有1的行中，剩余的N^2-1个数字每个只能出现一次，这意味着最多有(N^2-1)/(N-1)=N+1个唯一的行，因此矩阵包含1。 - outis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian · Accepted Answer

创建一个 64 x 64 x 8 的数组：bool forbidden[i][j][k]，用于指示对于第 k 行，是否出现过配对 (i,j)。每次在第 k 行使用配对 (i, j) 时，将该数组中对应的值设置为 1。请注意，你只会使用其中 i < j 的一半数组。

要构建新的置换，请从尝试成员0开始，并验证至少有七个未设置的 forbidden[0][j][0]。如果不足七个，则递增并重试。重复此过程以填充其余行。重复整个过程以填充整个 NxN 置换。

在实现此过程时，可能会有优化措施，但这样做应该已经足够好了。