自定义排列，对均等分布

Question

几个星期以来，我一直在处理一个奇怪的问题，似乎无法得到我想要的结果。

我想对对象列表进行排列以获得唯一的对。然后以特定方式对它们进行排序，以最大化列表中任何点的对象的平均分布。这也意味着如果一个对象在一对的开头，那么它也应该在不久之后在一对的结尾。没有配对可以重复。为了澄清，这里有一个例子。

list (A,B,C,D) 可能会导致以下结果：

(A,B)

(C,D)

(B,A)

(D,C)

(A,C)

(B,D)

(C,A)

(D,B)

(A,D)

(B,C)

(D,A)

(C,B)

请注意，每个字母每 2 对使用一次，并且字母频繁切换位置。

为了获得排列，我使用了 python 脚本：

perm = list(itertools.permutations(list,2))

这给了我 12 对字母。

然后我手动对这些对进行排序，以便尽可能多地选择每个字母并尽可能多地切换位置。在列表中的任何一点，这些字母都将非常平均地分配。当我完成解决这个问题的过程时，我知道我将在列表中的哪个位置停下来，但我不知道这对放置对的顺序有多大影响。

使用 4 个字母可以更容易地完成，因为 (4 个字母 / 2 对) = 2。我也希望这也适用于奇数排列对。

例如：

A,BC

甲、乙、丙、丁、乙

等等..

我已经尝试了多种方法并尝试识别模式，虽然有很多方法，但只有很多方法可以解决这个问题。也可能没有完美的答案。

我还尝试对字母 P(4,4) 或 5 个字母 P(5,5) 进行正常排列，并且我尝试选择某些排列，将它们组合起来，然后将它们分成对. 这似乎是另一条路线，但除非我手动完成，否则我似乎无法弄清楚要选择哪些对。

任何帮助表示赞赏！也许试着指出我正确的方向:)

我最终会尝试将其实现到 python 中，但我不一定需要帮助编写代码。这更多是一个过程可能是什么的问题。

Answer 1

您所说的“最大化平均分配”是什么意思没有明确定义。人们可能会考虑给定值的两个幻影之间的最大对数。我将留给你展示我在这里给出的方法相对于它是如何执行的。对于 n 个对象，我们有 n*(n-1) 对。在这些(a, b)对中：n 具有诸如 b = (a+1) modulo n 之类的索引n 具有诸如 b = (a+2) modulo n 之类的索引等等。我们可以生成前 n 对相差 1，然后生成 n 对相差 2...对于每个差异，我们通过将差异添加到索引（模 n）来生成索引。当我们得到a已经用于这种差异的an 时，我们加 1（再次取模 n）。这样，我们可以生成具有这种差异的 n 对。当我们“滚动”索引时，我们确信每个值都会定期出现。def pairs(n):&nbsp; &nbsp; for diff in range(1, n):&nbsp; &nbsp; &nbsp; &nbsp; starts_seen = set()&nbsp; &nbsp; &nbsp; &nbsp; index = 0&nbsp; &nbsp; &nbsp; &nbsp; for i in range(n):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pair = [index]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; starts_seen.add(index)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index = (index+diff) % n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pair.append(index)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield pair&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index = (index+diff) % n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if index in starts_seen:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index = (index+1) % n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;pairs2 = list(pair for pair in pairs(2))print(pairs2)# [[0, 1], [1, 0]]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;pairs3 = list(pair for pair in pairs(3))print(pairs3)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# [[0, 1], [2, 0], [1, 2],&nbsp;#&nbsp; [0, 2], [1, 0], [2, 1]]pairs4 = list(pair for pair in pairs(4))print(pairs4)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;# [[0, 1], [2, 3], [1, 2], [3, 0],&nbsp; &nbsp;<- diff = 1#&nbsp; [0, 2], [1, 3], [2, 0], [3, 1],&nbsp; &nbsp;<- diff = 2#&nbsp; [0, 3], [2, 1], [1, 0], [3, 2]]&nbsp; &nbsp;<- diff = 3pairs5 = list(pair for pair in pairs(5))print(pairs5)&nbsp; &nbsp;&nbsp;# [[0, 1], [2, 3], [4, 0], [1, 2], [3, 4],#&nbsp; [0, 2], [4, 1], [3, 0], [2, 4], [1, 3],#&nbsp; [0, 3], [1, 4], [2, 0], [3, 1], [4, 2],#&nbsp; [0, 4], [3, 2], [1, 0], [4, 3], [2, 1]]# A check to verify that we get the right number of different pairs:for n in range(100):&nbsp; &nbsp; pairs_n = set([tuple(pair) for pair in pairs(n)])&nbsp; &nbsp; assert len(pairs_n) == n*(n-1)print('ok')# ok