寻找一组排列的，有约束

Question

我有一组N ^ 2号和N个频点的。每个箱子应该从分配给它的一组有N个号码。我面临的问题是找到一组的数字映射到二进制位分布，满足约束，即每一对数字可以共享相同的仓只有一次。

一个分布可以很好地由一个NxN矩阵，其中每一行代表一个仓来表示。然后，问题是找到一组矩阵”的元件，其中每一对数字共享相同的行仅一次的排列。这是不相关的是哪一行，只有两个数字分别两者都转让给同一个。

实施例组3点的排列满足对N = 8的约束：

 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。

---

枚举三是容易的，它由1个任意置换，其置换和其中的行是由前一矩阵”对角线的矩阵。

我无法找到一种方法以产生一组包括更多虽然。这似乎是无论是非常复杂的问题，还是一个简单的问题，有不明显的解决方案。无论哪种方式，我很感激，如果有人有任何想法如何解决它在合理的时间为N = 8的情况下，还是发现了问题的正确和学术的名字，这样我就可以谷歌它。

如果你想知道什么是有用的，我正在寻找一个有8个缓冲器交叉开关，供应流量到64个目的地的调度算法。调度算法的这部分输入业务无关的，和多个硬连线目的地缓冲区映射之间周期性地进行切换。我们的目标是让每对目的地址的循环周期争用相同的缓冲只有一次，并最大限度那个时期的长度。换句话说，使每一对地址是为相同的缓冲液尽可能少的竞争。

---

编辑：

下面是一些代码，我有。 CODE

这是贪心，通常发现所述第三置换之后终止。但应该存在一组的至少N个排列满足问题的。

在替代方案将要求选择置换我涉及寻找排列（I + 1..N），以检查是否置换I是由排列的最大数量的解决方案的一部分。这会需要枚举所有排列，以检查在每一个步骤，这是非常昂贵的。

Answer 1

你想要的是一个组合块设计。链接页面上使用的术语，你想要的尺寸设计（N ^ 2，N，1）最大ķ。这会给你N（N + 1）置换，使用的命名。这是通过计数参数（请参见文章对于b的从V，k和拉姆达推导中的说明）的最大理论上可能。这种设计对于N = P ^ k代表一些素数p和整数k存在，则使用仿射平面。据推测，唯一存在的仿射飞机是这种规模的。因此，如果你可以选择N，也许这个答案就够了。

然而，如果不是最大的理论上可能数排列的，你只是想找到大量（最多可以为一个给定的n ^ 2），我不知道这些对象的研究中被调用。

Answer 2

请64×64×8的阵列：BOOL禁止[i] [j] [k]的指示对（i，j）的是否已经出现在第k行。每次在第k行使用对（i，j）的时间，就会在该数组中设置的值相关联的一个。请注意，将只使用这个数组，I

要构造一个新的置换，通过试图构件0开始，并验证禁止的[0] [j]的至少七个[0]是未设置。如果有，不是七左，增量和再试一次。重复填写该行的其余部分。重复这整个过程，以填充整个N×N个排列。

有可能优化你应该能够拿出你实现这一点，但是这应该做的相当不错。

Answer 3

也许你会重新制定您的问题到图论。例如，你开始用N×N个顶点的完全图。在每一步，你分区图分成N N-小集团，然后除去所使用的所有的边。

有关此N = 8的情况下，K64具有64×63/2 = 2016的边缘，和64批K8的具有1792层的边缘，所以你的问题的可能不是不可能的： - ）

Answer 4

右键，因为你跑出来的数字贪婪的风格不工作。

可以很容易地看到你违反约束之前，不可能有超过63个排列。在第64个，你就必须与另一个公司已经与配对的号码中至少一个。鸽巢原理。

在实际上，如果使用禁止对我早先提出的表，则发现有一个最大只有N + 1 = 9的排列可能是在运行之前。该表具有N ^ 2×（N ^ 2-1）/ 2 = 2016非冗余约束和每个新的置换将产生的N×（N选择2）= 28点新的配对。因此，所有的配对会后28分之2016= 9排列用完。这似乎是意识到有这么几个排列的关键是解决问题。

可以生成N-1编号为n = 0 N置换的列表...作为

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

，其通过每个排列中移位的列生成一个新的置换。第n个排列的最上面一行是第n-1置换的对角线。编辑：哎呀......这似乎只工作时，N为素数。

这最后错过一次置换中，您可以通过转置矩阵得到：

A_ij = j * N + i