algorithm - 寻找一组排列，有约束

Question

我有一组 N^2 个数字和 N 个箱子。每个箱子都应该有分配给它的集合中的 N 个数字。我面临的问题是找到一组将数字映射到 bin 的分布，满足约束，即每对数字只能共享同一个 bin 一次。

分布可以很好地用 NxN 矩阵表示，其中每一行代表一个 bin。然后问题是找到矩阵元素的一组排列，其中每对数字仅共享同一行一次。它在哪一行无关紧要，只是两个数字都分配给了同一个数字。

满足 N=8 约束的 3 个排列的示例集:

 0  1  2  3  4  5  6  7 8  9 10 11 12 13 14 1516 17 18 19 20 21 22 2324 25 26 27 28 29 30 3132 33 34 35 36 37 38 3940 41 42 43 44 45 46 4748 49 50 51 52 53 54 5556 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 配对成一行。

---

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

不过，我找不到制作包含更多内容的集合的方法。这似乎是一个非常复杂的问题，或者是一个解决方案不明显的简单问题。无论哪种方式，如果有人有任何想法如何在合理的时间内解决 N=8 的情况，或者确定问题的正确学术名称，以便我可以谷歌搜索，我将不胜感激。

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

---

编辑:

这是我的一些代码。 CODE

比较贪心，一般在找到第三个排列后就结束了。但至少应该存在一组满足问题的排列。

替代方案要求选择排列 I 涉及寻找排列 (I+1..N)，以检查排列 I 是否是包含最大排列数的解的一部分。这需要枚举所有排列以在每一步进行检查，这是非常昂贵的。

Answer 1

你想要的是一个combinatorial block design .使用链接页面上的命名法，您需要设计大小为 (n^2, n, 1) 的最大 k。这将使用您的命名法为您提供 n(n+1) 个排列。这是计数参数理论上可能的最大值(参见文章中关于从 v、k 和 lambda 推导 b 的解释)。对于一些质数 p 和整数 k，使用仿射平面的 n = p^k 存在这样的设计。据推测，唯一存在的仿射平面就是这种大小。因此，如果您可以选择 n，也许这个答案就足够了。

但是，如果您只想找到一个大数字(对于给定的 n^2，您可以找到的最大数字)而不是理论上可能的最大排列数，我不确定对这些对象的研究叫什么。