Сортировка списка кортежей, так что группировка по ключу не нужна

Question

У меня есть список идентификаторов, представляющих пользователей, и я пишу функцию, чтобы превратить этот список идентификаторов в расписание пользовательских сопоставлений (пар) :

ids = [1, 2, 3, 4] 

график, связанные с этим будет выглядеть так:

week 1: (1, 2), (3, 4) 
week 2: (1, 3), (2, 4) 
week 3: (1, 4), (2, 3) 
week 4: (1, 2), (3, 4) [repeat of week 1] 

и так далее. Я пытался сделать это с помощью вложенных for циклов на основе количества идентификаторов пользователей и комбинаций, полученных в результате этого.

ids = [1,2,3,4] 
matchups = [] 

#generate all the combinations of matchups 
for subset in itertools.combinations(ids,2): 
    matchups.append(subset) 

Это возвращает все потенциальные пары как список кортежей - отлично! В этом суть того, что я ищу. Моя проблема теперь выясняет, как превратить это во что-то полезное. Например, приведенный выше код возвращает этот список для matchups:

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 

Я пытался сложную рекурсивную функцию, чтобы создать список уникальных спариваний для каждой недели, потом я понял, что если у меня есть выше список в Правильный порядок, я могу просто использовать его, чтобы назначить пары от начала до конца, независимо от недели, и повторять, когда я дойду до конца. То есть, я могу просто назначить пары недель, используя известное количество спаев, необходимых в неделю, и известное количество недель.

С этой целью я пытался выяснить, как сортировать список кортежей на основе элементов, которые являются не равным. Метод sorted() имеет множество полезных реализаций такого типа ситуаций, но я могу получить результаты только в том случае, если результаты сгруппированы, например, выше.

Я хотел бы найти применение sorted(), который будет возвращать следующий, почти как анти-рода:

[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)] 

Есть ли способ использовать lambda для этого?

EDIT: Я только что понял, что 1-й элемент должен быть сопряжен с 6-м, 2-м, 5-м и 3-м с 4-м. Я не знаю, распространяется ли это на общий случай, но я ожидаю, что это возможно, потому что я предпринял другие шаги, чтобы гарантировать, что всегда есть четное число идентификаторов.

Теперь я уверен, что есть способ интерполировать список, чтобы достичь этого.

EDIT2: Похоже, предыдущая догадка не была правильной - она ​​не работает с 6 идентификаторами, и, вероятно, все, что за ее пределами, тоже потерпит неудачу. Я вернусь к тому, чтобы выяснить, есть ли способ разгона вместо сортировки на основе ключа

Answer 1

Это им Алгоритм турнира с круговым движением википедии.

x = range(1, 11) #10 players 

def round_robin(someIds): 
    someIds = someIds[::2] + someIds[1::2] 
    first, someIds = [someIds[0]], someIds[1:] 
    n = len(someIds) 
    for i in range(n): 
     top = someIds[:n/2] 
     bottom = someIds[n/2:] 
     yield zip(first+top, bottom) 
     someIds = someIds[-1:] + someIds[:-1] 


for thing in round_robin(x): 
    print thing 

Выход

[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)] 
[(1, 3), (4, 5), (6, 7), (8, 9), (10, 2)] 
[(1, 4), (5, 6), (7, 8), (9, 10), (2, 3)] 
[(1, 5), (6, 7), (8, 9), (10, 2), (3, 4)] 
[(1, 6), (7, 8), (9, 10), (2, 3), (4, 5)] 
[(1, 7), (8, 9), (10, 2), (3, 4), (5, 6)] 
[(1, 8), (9, 10), (2, 3), (4, 5), (6, 7)] 
[(1, 9), (10, 2), (3, 4), (5, 6), (7, 8)] 
[(1, 10), (2, 3), (4, 5), (6, 7), (8, 9)] 

Answer 2

Я считаю, что вы ищете канонический алгоритм планирования round-robin.

Список ваших игроков в любом порядке найти удобный, в два ряда:

1 2 3 4 
5 6 7 8 

Ваш первый круглый спариваний являются 1-5, 2-6, 3-7, 4-8. В течение последующих недель поворачивайте все, кроме позиции # 1: верхняя строка сдвигается влево, нижняя строка сдвигается вправо; те, которые падают с конца (2 и 8) двигаться вверх/вниз на пустое место:

1 3 4 8 
2 5 6 7 

Если вам также необходимо сбалансировать дом вдали спариваний, то после того, как вы закончите с этим езда на велосипеде, вернуться и обменивайте строки каждую неделю.

Answer 3

Потенциально унииоматическое решение, но оно работает. Может быть, кто-то может сделать его более питоническим? : D

def antisort(x): 
    if len(x) > 0: 
     return [x[0]] + antisort(x[-1:0:-1]) 
    else: 
     return [] 

>>> antisort([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]) 
[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)] 

Этот кусочек нотация просто принимает все после первого элемента и меняет его:

x[-1:0:-1] 

Answer 4

Это то, что я имел в виду мой комментарий:

a = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 
new = [] 

i, j = len(a)-1, 0 

for n in range(i+1): 
    if n % 2: 
     new.append(a[i]) 
     i -= 1 
    else: 
     new.append(a[j]) 
     j += 1 

print(new) 

Выход:

[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)]