自定义排列，对的均等分布 [英] Custom permutation, Equal distribution of pairs

问题描述

我一直在玩一个奇怪的问题，已经有几个星期了，似乎无法获得想要的结果.

I've been playing with a strange problem for a few weeks and can't seem to get the results I want.

我想对对象列表进行排列以获得唯一的对.然后以特定方式对它们进行排序，以使对象在列表中的任何点处的均等分布最大化.这也意味着，如果一个对象在一对的开始处，则也应该在一对之后的结束处.没有对可以重复.为了澄清，这是一个示例.

I'd like to take a permutation of a list of objects to get unique pairs. Then order them in a particular way to maximize equal distribution of the objects at any point in the list. This also means that if an object is at the beginning of a pair if should also be at the end of a pair soon after. No pairs can repeat. To clarify, here is an example.

列表(A，B，C，D)可能会导致以下结果:

list (A,B,C,D) might result in the following:

(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对使用一次，并且字母频繁切换位置.

Notice, every letter is used every 2 pairs, and the letters switch positions frequently.

要获得排列，我使用了python脚本:

To get the permutation I used the python script:

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

给了我12对信.

然后，我手动排序对，以便尽可能经常地选择每个字母，并尽可能频繁地切换位置.在列表中的任何时候，字母将非常平均地分布.当我解决这个问题的过程时，我知道我将在列表中的哪个位置停止，但是我不知道这对配对的放置顺序有多大影响.

I then manually ordered the pairs so the each letter is chosen as often as possible and switches position as often as possible. At any point in the list the letters will be distributed very equally. When I go through the process of figuring out this problem I know where in the list I will stop but I don't know how much that effects the order the pairs are placed in.

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

With 4 letters it can be done easier because (4 letters / 2 pairs) = 2. I also would like this to work with odd permutation pairs as well.

例如:

A，B.C

A，B，C，D，E

A,B,C,D,E

等.

我已经尝试了许多方法并尝试识别模式，尽管有很多方法，但是尤其有很多方法可以解决此问题.可能还没有一个完美的答案.

I have tried this a number of ways and tried to recognize patterns and while there are plenty, there is just many ways to do this problem especially. There also may not be a perfect answer.

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

I have also tried taking a normal permutation of the letters P(4,4) or in the case of 5 letters P(5,5), and I've tried picking certain permutations, combining them, and then chopping them up into pairs. This seems like another route but I can't seem to be able to figure out which pairs to pick unless I manually work through it.

感谢您的帮助！也许尝试为我指出正确的方向:)

Any help is appreciated! Maybe try to point me in the right direction :)

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

I ultimately will try to implement this into python but I don't necessarily need help writing the code. it's more a question of what the process might be.

推荐答案

最大化平均分配"的含义尚未明确定义.一个给定值的两个幻影之间可以考虑的最大对数.我会留给您展示一下我在这里给出的方法相对于此的效果.

What you mean by 'maximize equal distribution' isn't clearly defined. One could maybe consider the greatest number of pairs between two apparitions of a given value. I'll leave it to you to show how the method I give here performs relatively to that.

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

With n objects, we have n*(n-1) pairs. In these (a, b) pairs:

• n具有诸如b =(a + 1)模n的索引

• n的索引为b =(a + 2)模n

• n have indices such as b = (a+1) modulo n

• n have indices such as b = (a+2) modulo n

以此类推.

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

We can generate the first n pairs with a difference of 1, then the n pairs with a difference of 2...

对于每个差异，我们通过将差异添加到索引(模n)来生成索引.当我们得到已经用于此差异的a时，我们加1 (再次取模n).这样，我们可以产生具有这种差异的n对.当我们在索引中滚动"时，我们确定每个值都会定期出现.

For each difference, we generate the indices by adding the difference to the index (modulo n). When we get an a that was already used for this difference, we add 1 (modulo n, again). This way, we can generate the n pairs with this difference. As we are 'rolling' through the indices, we are sure that every value will appear regularly.

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

这篇关于自定义排列，对的均等分布的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！