python : speed dating & permutation
Question: I have 36 persons and 6 tables. I'd like to form 6 groups around each table.
Then form 6 other groups and 6 others again and again... until everybody met
everybody but nobody met someone twice.

So far I came up with this script, but it produces repetitions :

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

and the output is :

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

Can someone explain me why ? And maybe how to get the result ? Thanks a lot!


Answer: > **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
> <http://math.stackexchange.com/questions/924326/diner-permutations>

To satisfy the requirements, that everyone sits together, and never sits with
the same person twice, you need N+1 rounds.

I came up with the following algorithm by working it out on paper with 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
    --
    

The algorithm works as follows: in each successive round `i`, build row `j` by
tracing the diagonal from the current `0th` element in that row, wrapping
around diagonally. You can trace this visually in the first three rounds. The
last round is a transposition of the initial matrix, because these "columns"
never have a chance to mix. In the program below we print the transposition
first.

Here's the code:

    
    
    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)
    

Here's the output from this program:

    
    
    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:** with the automated test, this is the output

    
    
    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 does have
[`itertools.permutations`](https://docs.python.org/2/library/itertools.html#itertools.permutations),
but it's not very useful in this case, as we don't want _all_ permutations, we
just want a set of permutations that satisfy the requirements.

