python : speed dating & permutation

Question

我有 36 个人和 6 张 table 。我想围绕每张 table 组成 6 个小组。然后再组成 6 个其他组，再组成 6 个其他组……直到每个人都遇到每个人，但没有人遇到两次。

到目前为止，我想出了这个脚本，但它会产生重复:

people = [ [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] ]

def perm():
    z = 0
    for X in people:
        for r in range(0,z):
            f = X.pop()
            X.insert(0,f)
        z +=1

def calcul():        
    for q in range(0,6):
        table_1 = []
        table_2 = []
        table_3 = []
        table_4 = []
        table_5 = []
        table_6 = []

        for r in range(0,6):
            table_1.append(people[r][0])
            table_2.append(people[r][1])
            table_3.append(people[r][2])
            table_4.append(people[r][3])
            table_5.append(people[r][4])
            table_6.append(people[r][5])

        print(table_1)
        print(table_2)
        print(table_3)
        print(table_4)
        print(table_5)
        print(table_6)
        print '--'

        perm()


calcul()

输出是:

[1, 7, 13, 19, 25, 31]
[2, 8, 14, 20, 26, 32]
[3, 9, 15, 21, 27, 33]
[4, 10, 16, 22, 28, 34]
[5, 11, 17, 23, 29, 35]
[6, 12, 18, 24, 30, 36]
--
[1, 12, 17, 22, 27, 32]
[2, 7, 18, 23, 28, 33]
[3, 8, 13, 24, 29, 34]
[4, 9, 14, 19, 30, 35]
[5, 10, 15, 20, 25, 36]
[6, 11, 16, 21, 26, 31]
--
[1, 11, 15, 19, 29, 33]
[2, 12, 16, 20, 30, 34]
[3, 7, 17, 21, 25, 35]
[4, 8, 18, 22, 26, 36]
[5, 9, 13, 23, 27, 31]
[6, 10, 14, 24, 28, 32]
--
[1, 10, 13, 22, 25, 34]
[2, 11, 14, 23, 26, 35]
[3, 12, 15, 24, 27, 36]
[4, 7, 16, 19, 28, 31]
[5, 8, 17, 20, 29, 32]
[6, 9, 18, 21, 30, 33]
--
[1, 9, 17, 19, 27, 35]
[2, 10, 18, 20, 28, 36]
[3, 11, 13, 21, 29, 31]
[4, 12, 14, 22, 30, 32]
[5, 7, 15, 23, 25, 33]
[6, 8, 16, 24, 26, 34]
--
[1, 8, 15, 22, 29, 36]
[2, 9, 16, 23, 30, 31]
[3, 10, 17, 24, 25, 32]
[4, 11, 18, 19, 26, 33]
[5, 12, 13, 20, 27, 34]
[6, 7, 14, 21, 28, 35]
--

谁能解释一下为什么？也许如何得到结果？非常感谢!

Answer 1

Edit: It appears the following algorithm works only for odd N

Edit2: I've updated the code to include an automated test of the requirements. This algorithm only works if N is prime You can verify this by running the program with any prime number for N, and its odd successor, e.g. 53 and 55 (comment out print_table_perms in this case!)

Edit3: Apparently this is a famous open problem in Mathematics https://math.stackexchange.com/questions/924326/diner-permutations

要满足大家坐在一起，而且绝不会和同一个人坐两次，需要N+1轮。

我通过在纸上用 N=3 计算出以下算法

1 2 3
4 5 6
7 8 9
--
1 5 9
4 8 3
7 2 6
--
1 8 6
4 2 9
7 5 3
--
1 4 7
2 5 8
3 6 9
--

该算法的工作原理如下:在每一轮 i 中，通过从当前 第 0 元素追踪对角线来构建行 j行，沿对角线环绕。您可以在前三轮中直观地跟踪这一点。最后一轮是初始矩阵的转置，因为这些“列”永远没有机会混合。在下面的程序中，我们首先打印转置。

代码如下:

from copy import deepcopy

def gen_tables(N):
    tables = []
    x = 1
    for i in xrange(N):
        tables.append(range(x, x + N))
        x += N
    return tables

def print_tables(tables):
    for table in tables:
        print " ".join(map(str, table))
    print

def print_table_perms(perms):
    for perm in perms:
        print_tables(perm)

def gen_table_perms(tables):
    perms = []

    N = len(tables[0])

    for table in tables:
        assert(len(table) == N)
    
    # first, add the "columns", who won't be mixed together
    perms.append(map(list, zip(*tables)))

    current_tables = deepcopy(tables)
    next_tables = deepcopy(tables)
    
    # next, mix the columns with a diagonal shift (mod N)
    for i in xrange(N):
        perms.append(deepcopy(current_tables))

        for j in xrange(N):
            for k in xrange(N):
                next_tables[j][k] = current_tables[(j + k) % N][k]

        (current_tables, next_tables) = (next_tables, current_tables)

    return perms

def verify_table_perms(perms):
    N = len(perms[0][0])

    expect = set((x for x in xrange(1, N * N + 1)))

    v = {}
    for i in xrange(1, N * N + 1):
        v[i] = set((i,))

    for perm in perms:
        for table in perm:
            for seat in table:
                v[seat].update(table)

    for s in v.values():
        assert s == expect, s

tables = gen_tables(6)
perms = gen_table_perms(tables)
verify_table_perms(perms)
print_table_perms(perms)

这是这个程序的输出:

1 7 13 19 25 31
2 8 14 20 26 32
3 9 15 21 27 33
4 10 16 22 28 34
5 11 17 23 29 35
6 12 18 24 30 36
--
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
--
1 8 15 22 29 36
7 14 21 28 35 6
13 20 27 34 5 12
19 26 33 4 11 18
25 32 3 10 17 24
31 2 9 16 23 30
--
1 14 27 4 17 30
7 20 33 10 23 36
13 26 3 16 29 6
19 32 9 22 35 12
25 2 15 28 5 18
31 8 21 34 11 24
--
1 20 3 22 5 24
7 26 9 28 11 30
13 32 15 34 17 36
19 2 21 4 23 6
25 8 27 10 29 12
31 14 33 16 35 18
--
1 26 15 4 29 18
7 32 21 10 35 24
13 2 27 16 5 30
19 8 33 22 11 36
25 14 3 28 17 6
31 20 9 34 23 12
--
1 32 27 22 17 12
7 2 33 28 23 18
13 8 3 34 29 24
19 14 9 4 35 30
25 20 15 10 5 36
31 26 21 16 11 6
--

Edit2:通过自动化测试，这是输出

Traceback (most recent call last):
  File "table_perms.py", line 65, in <module>
    verify_table_perms(perms)
  File "table_perms.py", line 61, in verify_table_perms
    assert s == expect, s
AssertionError: set([1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 17, 18, 19, 20, 22, 24, 25, 26, 27, 29, 30, 31, 32, 36])

Python 确实有 itertools.permutations , 但在这种情况下它不是很有用，因为我们不想要 所有 排列，我们只想要一组满足要求的排列。