Làm thế nào để (hiệu quả) tạo ra các bộ phân tách trong khi sử dụng các cặp phần tử chỉ một lần?

Question

Những gì tôi muốn làm là chia một nhóm (n) Các thành các nhóm kích thước bằng nhau (nhóm kích thước m, và vì đơn giản giả định rằng không có thức ăn thừa, tức là n là chia hết cho bởi m). Làm điều này nhiều lần, tôi muốn đảm bảo rằng không có cặp mục nào trong cùng một nhóm với nhau hai lần.

Để làm cho bê tông nhẹ hơn này, để xây dựng nhóm của hai trong số sáu mục A..F, một khi có thể phân vùng tập gấp năm lần theo những cách khác nhau:

• (A, B), (C, D), (E, F)
• (A, C), (B, E), (D, F)
• (A, D), (B, F), (C, E)
• (A, E), (B, D), (C, F)
• (A, F), (B, C), (D, E)

Tập cùng các mặt hàng có thể được phân chia một lần duy nhất vào nhóm của ba mà không cặp chồng chéo:

• (A, B, C), (D, E, F)

_{(Như @DavidHam người đàn ông chỉ ra dưới đây, có nhiều cách khác nhau để tạo phân vùng trong ví dụ này. Tuy nhiên, khi đã tạo phân vùng một lần, không bao giờ có một phân vùng thứ hai nào tách tất cả các cặp. Đó là tốt - ứng dụng của tôi không cần phải tạo ra tất cả có thể cách phân vùng bộ trên toàn thế giới, một cuộc họp giải pháp những hạn chế sẽ làm)}

---

Câu hỏi của tôi, bây giờ, là thế này: Có một cách làm điều này hiệu quả? Có thủ thuật nào để tăng tốc độ tạo ra các bộ này không?

Vì vậy, đến nay, tôi đã xử lý vấn đề này như là một vấn đề exact cover và giải quyết nó bằng backtracking algorithm (một biến thể của DLX). Điều này làm việc rất tốt cho các cặp, nhưng khi các nhóm trở nên lớn hơn số lượng các khả năng thuật toán phải xem xét phát nổ, và xử lý trở nên rất khó sử dụng.

Điều tôi đang tìm kiếm là các mẹo để tăng tốc mọi thứ lên. Bất cứ ý tưởng là rất đáng hoan nghênh, đặc biệt (nhưng không giới hạn):

• tối ưu hóa và chẩn đoán để giảm số lượng các khả năng mà cần phải được xem xét trước khi giải quyết (ví dụ, nó là rõ ràng từ các ví dụ ở trên, việc phân chia đầu tiên có thể được thực hiện đơn giản tùy ý, và tập đầu tiên của mỗi phân vùng [cột đầu tiên ở trên] có thể được tạo tự động).
• Có các biến thể của backtracking có thể đối phó với số lượng lớn các ứng cử viên? (ví dụ: không cần phải tạo mọi khả năng trước)
• Các thuật toán khác , phương pháp tiếp cận hoặc khái niệm toán học mà tôi nên xem xét?

Bất kỳ ý tưởng và đề xuất nào đều được hoan nghênh. Cảm ơn bạn rất nhiều vì đã cân nhắc điều này!

---

Cập nhật

Ok, vì vậy đây đã được một thời gian, nhưng tôi đã dành nhiều thời gian hơn về vấn đề này và muốn lấy lại cho bạn. @ david-eisenstat đặt tôi vào đúng con đường bằng cách cho tôi cụm từ tìm kiếm chính xác (cảm ơn bạn rất nhiều!) - Tôi đã đọc khá một chút về vấn đề Golfer xã hội.

Một trong những nguồn tài nguyên tốt nhất mà tôi tìm thấy, là tác phẩm của Markus Triska, người thảo luận về một số phương pháp tiếp cận (và sau đó tiếp tục trình bày thuật toán rất hay) trong luận án của mình. Điều này là rất khuyến khích nếu bất cứ ai chạy vào một vấn đề tương tự!

Answer 1

Sự cố này được nghiên cứu với tên Social Golfer Problem. Tài liệu có kích thước không phát triển, nhưng có ba cách tiếp cận chính:

1. Phương pháp tìm kiếm địa phương có thể xử lý các trường hợp không có nhiều cặp.

2. Hoàn thành các phương pháp tìm kiếm như giảm của bạn để bao gồm chính xác. Từ những gì tôi nhớ, nghiên cứu ở đây xoay quanh các phương pháp hiệu quả để phá vỡ tính đối xứng, trong đó ý tưởng của bạn về việc sửa hàng đầu tiên có lẽ là đơn giản nhất.

3. Công trình toán học. Khi q là một lũy thừa nguyên tố, có một phép xây dựng cho q nhóm q liên quan đến finite affine planes không quá khủng khiếp để thực hiện. Ngoài ra, có rất nhiều công trình một lần. Sổ tay về kiểu dáng kết hợp có lẽ là cách tốt nhất để tóm tắt những gì đã biết.

Answer 2

Hãy để n=m*k, phân vùng có m các nhóm có k mục.

Sau khi phân vùng x, mỗi mục nằm trong một nhóm với x*(k-1) các mục khác. Sau khi tạo phân vùng t-1, trong phân vùng tiếp theo A có thể chọn cho:

second element : n - (t-1)*(k-1) - 1 items 
third element : n - 2*(t-1)*(k-1) - 2 items 
fourth element : n - 3*(t-1)*(k-1) - 3 items 
... 
k'th element : n - (t-1)*(k-1)^2 - (k-1) items 

Để tạo phân vùng t'th chúng ta cần:

n - (t-1)*(k-1)^2 - (k-1) > 0 
=> 
t < (n - k + 1)/((k-1)^2) + 1 

Số phân vùng có thể giảm với bình phương của chiều dài nhóm. Điều đó có nghĩa là không có quá nhiều phân vùng có thể :-)

Tôi sẽ đi với một số cách tiếp cận tham lam. Lưu trữ cho từng bộ mục có sẵn và tạo phân vùng mới bằng cách thêm mục sẵn có đầu tiên vào nhóm.