自定义排列，对均等分布

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):

    for diff in range(1, n):

        starts_seen = set()

        index = 0

        for i in range(n):

            pair = [index]

            starts_seen.add(index)

            index = (index+diff) % n

            pair.append(index)

            yield pair

            index = (index+diff) % n

            if index in starts_seen:

                index = (index+1) % n

                

pairs2 = list(pair for pair in pairs(2))

print(pairs2)

# [[0, 1], [1, 0]]          

pairs3 = list(pair for pair in pairs(3))

print(pairs3)         

# [[0, 1], [2, 0], [1, 2], 

#  [0, 2], [1, 0], [2, 1]]

pairs4 = list(pair for pair in pairs(4))

print(pairs4)        

# [[0, 1], [2, 3], [1, 2], [3, 0],   <- diff = 1

#  [0, 2], [1, 3], [2, 0], [3, 1],   <- diff = 2

#  [0, 3], [2, 1], [1, 0], [3, 2]]   <- diff = 3

pairs5 = list(pair for pair in pairs(5))

print(pairs5)    

# [[0, 1], [2, 3], [4, 0], [1, 2], [3, 4],

#  [0, 2], [4, 1], [3, 0], [2, 4], [1, 3],

#  [0, 3], [1, 4], [2, 0], [3, 1], [4, 2],

#  [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):

    pairs_n = set([tuple(pair) for pair in pairs(n)])

    assert len(pairs_n) == n*(n-1)

print('ok')

# ok