自定义排列，对等分布

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,B.C

A,B,C,D,E

等..

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

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

感谢任何帮助！也许试着给我指出正确的方向:)

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

Answer 1

您所说的 'maximize equal distribution' 没有明确定义。人们也许可以考虑给定值的两个幻影之间的最大对数。我会留给你展示我在这里给出的方法相对于那个方法如何执行。

对于 n 个对象，我们有 n*(n-1) 对。在这些 (a, b) 对中：

n 有 b = (a+1) modulo n
这样的索引
n 的索引如 b = (a+2) modulo n

等等。

我们可以生成差值为 1 的前 n 对，然后是差值为 2 的 n 对...

对于每个差异，我们通过将差异添加到索引（模 n）来生成索引。当我们得到一个已经用于此差异的 a 时，我们添加 1 （再次对 n 取模）。这样，我们就可以生成具有这种差异的 n 对。由于我们正在 'rolling' 通过索引，我们确信每个值都会定期出现。

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

自定义排列，对等分布

Custom permutation, Equal distribution of pairs

python

language-agnostic

permutation

combinatorics

discrete-mathematics