python: скорость знакомства и перестановка

Question

У меня есть 36 человек и 6 столов. Я бы хотел сформировать 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

Редактировать: Похоже, следующий алгоритм работает только для нечетного N

Edit2: Я обновил код, чтобы включить автоматическую проверку требований. Этот алгоритм работает только в том случае, если N prime Вы можете проверить это, запустив программу с любым простым номером для N и его нечетным преемником, например. 53 и 55 (закомментировать print_table_perms в этом случае!)

Edit3: Видимо это известная открытая проблема в математике 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, построить ряд j прослеживая по диагонали от тока 0th элемент в этой строке, обертывание по диагонали. Вы можете проследить это визуально в течение первых трех раундов. Последний раунд - это перенос исходной матрицы, потому что эти «столбцы» никогда не имеют возможности смешать. В приведенной ниже программе мы сначала печатаем транспонирование.

Вот код:

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, но это не очень полезно в этом случае, так как мы не хотим всех перестановок, нам просто нужен набор перестановок, которые удовлетворяют требованиям.