Tạo tất cả các hoán vị cặp duy nhất

Question

Tôi cần tạo tất cả các cặp có thể, nhưng với ràng buộc rằng một cặp đôi cụ thể chỉ xảy ra một lần trong kết quả. Ví dụ:

import itertools 

for perm in itertools.permutations(range(9)): 
    print zip(perm[::2], perm[1::2]) 

tạo tất cả các hoán vị hai cặp có thể có; đây là một tập con nhỏ của đầu ra:

... 
[(8, 4), (7, 6), (5, 3), (0, 2)] 
[(8, 4), (7, 6), (5, 3), (1, 0)] 
[(8, 4), (7, 6), (5, 3), (1, 2)] 
[(8, 4), (7, 6), (5, 3), (2, 0)] 
[(8, 4), (7, 6), (5, 3), (2, 1)] 
[(8, 5), (0, 1), (2, 3), (4, 6)] 
[(8, 5), (0, 1), (2, 3), (4, 7)] 
[(8, 5), (0, 1), (2, 3), (6, 4)] 
[(8, 5), (0, 1), (2, 3), (6, 7)] 
[(8, 5), (0, 1), (2, 3), (7, 4)] 
[(8, 5), (0, 1), (2, 3), (7, 6)] 
[(8, 5), (0, 1), (2, 4), (3, 6)] 
[(8, 5), (0, 1), (2, 4), (3, 7)] 
[(8, 5), (0, 1), (2, 4), (6, 3)] 
... 

Làm cách nào để lọc thêm nó để tôi chỉ thấy (8.4) một lần (trong suốt tất cả các hoán vị đã lọc) và (8.5) chỉ một lần và (0,1) chỉ một lần, và (4,7) chỉ một lần, vv?

Về cơ bản, tôi muốn các hoán vị sao cho mỗi kết hợp hai phần tử chỉ xảy ra một lần.

Tôi sẽ đặt cược có một công cụ bổ sung có thể giải quyết vấn đề này nhưng tôi không đủ chuyên môn để biết nó là gì.

Cập nhật: Gareth Rees là chính xác - Tôi hoàn toàn không biết rằng tôi đang cố gắng giải quyết vấn đề round-robin. Tôi có một hạn chế bổ sung đó là những gì tôi đang làm là nhóm người cho các bài tập lập trình cặp. Vì vậy, nếu tôi có một số lượng người lạ, tôi cần phải tạo một nhóm ba người để bao gồm một người kỳ quặc cho mỗi bài tập. Suy nghĩ hiện tại của tôi là (1) làm cho một số người thậm chí bằng cách thêm vào một người vô hình. Sau đó, sau khi ghép nối, tìm người được ghép nối với người vô hình và đặt ngẫu nhiên họ vào một nhóm hiện có để tạo thành một nhóm gồm ba người. Tuy nhiên, tôi tự hỏi nếu không có một thuật toán hoặc điều chỉnh để round-robin mà làm điều này một cách tốt hơn.

Cập nhật 2: Giải pháp của Theodros tạo ra kết quả chính xác mà không có sự ngập ngừng không thích hợp về tôi mô tả ở trên. Mọi người đều rất hữu ích.

Answer 1

tôi muốn chia sẻ một thực hiện khác nhau của lịch round-robin mà làm cho việc sử dụng cấu trúc deque -data từ Thư viện Tiêu chuẩn:

from collections import deque 

def round_robin_even(d, n): 
    for i in range(n - 1): 
     yield [[d[j], d[-j-1]] for j in range(n/2)] 
     d[0], d[-1] = d[-1], d[0] 
     d.rotate() 

def round_robin_odd(d, n): 
    for i in range(n): 
     yield [[d[j], d[-j-1]] for j in range(n/2)] 
     d.rotate() 

def round_robin(n): 
    d = deque(range(n)) 
    if n % 2 == 0: 
     return list(round_robin_even(d, n)) 
    else: 
     return list(round_robin_odd(d, n)) 


print round_robin(5) 
    [[[0, 4], [1, 3]], 
    [[4, 3], [0, 2]], 
    [[3, 2], [4, 1]], 
    [[2, 1], [3, 0]], 
    [[1, 0], [2, 4]]] 


print round_robin(2) 
    [[[0, 1]]] 

Nó đặt các đối tượng (ints here) vào deque. Sau đó, nó quay và xây dựng các cặp liên tiếp lấy từ cả hai đầu về phía giữa. Người ta có thể tưởng tượng điều này như gấp deque ở giữa trở lại chính nó. Để làm cho nó rõ ràng:

Trường hợp các yếu tố không đồng đều:

round 1  round 2  # pairs are those numbers that sit 
---------- ---------  # on top of each other 
0 1 2 3 4 8 0 1 2 3 
8 7 6 5  7 6 5 4 

Trong trường hợp thậm chí yếu tố một bước bổ sung là cần thiết.
(Tôi bỏ lỡ lần đầu tiên vì tôi chỉ kiểm tra trường hợp không đồng đều. Điều này mang lại một thuật toán sai khủng khiếp ... cho tôi thấy tầm quan trọng của việc kiểm tra các trường hợp cạnh khi triển khai thuật toán ...)
Bước đặc biệt này là rằng tôi trao đổi hai phần tử ngoài cùng bên trái (là phần tử đầu tiên và cuối cùng của deque) trước mỗi vòng quay - điều này có nghĩa là 0 vẫn ở trên cùng bên trái.

trường hợp thậm chí yếu tố:

round 1  round 2  # pairs are those numbers that sit 
---------- ---------  # on top of each other 
0 1 2 3  0 7 1 2 
7 6 5 4  6 5 4 3 

gì ám ảnh tôi về phiên bản này số lượng trùng lặp code đang, nhưng tôi không thể tìm thấy một cách để cải thiện trong khi vẫn giữ nó như là có thể đọc được. Dưới đây là thực hiện đầu tiên của tôi, đó là ít có thể đọc được IMO:

def round_robin(n): 
    is_even = (n % 2 == 0) 
    schedule = [] 
    d = deque(range(n)) 
    for i in range(2 * ((n - 1)/2) + 1): 
     schedule.append(
         [[d[j], d[-j-1]] for j in range(n/2)]) 
     if is_even: 
      d[0], d[-1] = d[-1], d[0] 
     d.rotate() 
    return schedule 

Cập nhật vào tài khoản cho câu hỏi Cập nhật:

Để cho phép trong trường hợp không đồng đều cho các nhóm của ba bạn chỉ cần thay đổi round_robin_odd(d, n):

def round_robin_odd(d, n): 
    for i in range(n): 
     h = [[d[j], d[-j-1]] for j in range(n/2)] 
     h[-1].append(d[n/2]) 
     yield h 
     d.rotate() 

Điều này cho phép:

print round_robin(5) 
[[[0, 4], [1, 3, 2]], 
[[4, 3], [0, 2, 1]], 
[[3, 2], [4, 1, 0]], 
[[2, 1], [3, 0, 4]], 
[[1, 0], [2, 4, 3]]] 

Answer 2

Chuyển danh sách sang set để đảm bảo mỗi bộ chỉ tồn tại một lần.

>>> from itertools import permutations 
>>> set([ zip(perm[::2], perm[1::2]) for perm in permutations(range(9)) ]) 
set([(7, 3), (4, 7), (1, 3), (4, 8), (5, 6), (2, 8), (8, 0), (3, 2), (2, 1), (6, 2), (1, 6), (5, 1), (3, 7), (2, 5), (8, 5), (0, 3), (5, 8), (4, 0), (1, 2), (3, 8), (3, 1), (6, 7), (2, 0), (8, 1), (7, 6), (3, 0), (6, 3), (1, 5), (7, 2), (3, 6), (0, 4), (8, 6), (3, 5), (4, 1), (6, 4), (5, 4), (2, 6), (8, 2), (2, 7), (7, 1), (4, 5), (8, 3), (1, 4), (6, 0), (7, 5), (2, 3), (0, 7), (8, 7), (4, 2), (1, 0), (0, 8), (6, 5), (4, 6), (0, 1), (5, 3), (7, 0), (6, 8), (3, 4), (6, 1), (5, 7), (5, 2), (0, 2), (7, 4), (0, 6), (1, 8), (4, 3), (1, 7), (0, 5), (5, 0), (7, 8), (2, 4), (8, 4)]) 

Từ mô tả của bạn, bạn muốn mỗi người trong số các hoán vị 2-tuple của range(9) ở trên sẽ cho bạn tất cả các hoán vị khác nhau, dựa trên mã của bạn. Nhưng, điều này là khá kém hiệu quả.

Tuy nhiên bạn có thể tiếp tục đơn giản hóa mã của bạn bằng cách làm như sau:

>>> list(permutations(range(9), 2)) 
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (4, 8), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7)] 

Phương pháp permutations cũng có một cuộc tranh luận dài mà sẽ cho phép bạn chỉ định độ dài của tuple trả lại. Do đó, bạn đã sử dụng đúng chức năng được cung cấp itertool nhưng đã bỏ qua tham số chiều dài tuple.

itertools.permutations documentation

Answer 3

Như MatthieuW nói trong this answer, có vẻ như nếu bạn đang cố gắng để tạo ra một lịch trình cho một round-robin tournament. Điều này có thể dễ dàng tạo ra bằng cách sử dụng this algorithm, khó khăn chính là việc xử lý một số lẻ của các đội (khi mỗi đội được tạm biệt trong một vòng).

def round_robin_schedule(n): 
    """ 
    Generate a round-robin tournament schedule for `n` teams. 
    """ 
    m = n + n % 2    # Round up to even number. 
    for r in xrange(m - 1): 
     def pairing(): 
      if r < n - 1: 
       yield r, n - 1 
      for i in xrange(m // 2 - 1): 
       p, q = (r + i + 1) % (m - 1), (m + r - i - 2) % (m - 1) 
       if p < n - 1 and q < n - 1: 
        yield p, q 
     yield list(pairing()) 

Ví dụ, với chín đội:

>>> list(round_robin_schedule(9)) 
[[(0, 8), (2, 7), (3, 6), (4, 5)], 
[(1, 8), (2, 0), (4, 7), (5, 6)], 
[(2, 8), (3, 1), (4, 0), (6, 7)], 
[(3, 8), (4, 2), (5, 1), (6, 0)], 
[(4, 8), (5, 3), (6, 2), (7, 1)], 
[(5, 8), (6, 4), (7, 3), (0, 1)], 
[(6, 8), (7, 5), (0, 3), (1, 2)], 
[(7, 8), (0, 5), (1, 4), (2, 3)], 
[(0, 7), (1, 6), (2, 5), (3, 4)]]