Thuật toán santa bí mật

Question

Mỗi Giáng sinh, chúng tôi vẽ tên cho trao đổi quà tặng trong gia đình mình. Điều này thường liên quan đến mulitple vẽ lại cho đến khi không có ai đã kéo vợ/chồng của họ. Vì vậy, năm nay tôi mã hóa tên của riêng tôi vẽ ứng dụng mà mất trong một loạt các tên, một loạt các cặp đôi không được phép, và gửi một email cho tất cả mọi người với người được tặng của họ đã chọn.

Ngay bây giờ, các thuật toán làm việc như thế này (trong giả):

function DrawNames(list allPeople, map disallowedPairs) returns map 
    // Make a list of potential candidates 
    foreach person in allPeople 
     person.potentialGiftees = People 
     person.potentialGiftees.Remove(person) 
     foreach pair in disallowedPairs 
      if pair.first = person 
       person.Remove(pair.second) 

    // Loop through everyone and draw names 
    while allPeople.count > 0 
     currentPerson = allPeople.findPersonWithLeastPotentialGiftees 
     giftee = pickRandomPersonFrom(currentPerson.potentialGiftees) 
     matches[currentPerson] = giftee 
     allPeople.Remove(currentPerson) 
     foreach person in allPeople 
      person.RemoveIfExists(giftee) 

    return matches 

Có ai người hiểu biết thêm về lý thuyết đồ thị biết một số loại thuật toán mà sẽ làm việc tốt hơn ở đây? Vì mục đích của tôi, công trình này, nhưng tôi tò mò.

CHỈNH SỬA: Vì email đã hết một lúc trước và tôi chỉ hy vọng tìm hiểu điều gì đó tôi sẽ thuật lại câu hỏi này thành câu hỏi lý thuyết đồ thị. Tôi không quá quan tâm đến những trường hợp đặc biệt mà các loại trừ là tất cả các cặp (như vợ chồng không nhận được nhau). Tôi quan tâm nhiều hơn đến những trường hợp có đủ loại trừ để tìm ra giải pháp nào trở thành phần khó khăn. Thuật toán của tôi ở trên chỉ là một thuật toán tham lam đơn giản mà tôi không chắc chắn sẽ thành công trong mọi trường hợp.

Bắt đầu với đồ thị được chỉ dẫn hoàn chỉnh và danh sách các cặp đỉnh. Đối với mỗi cặp đỉnh, loại bỏ cạnh từ đỉnh đầu tiên đến đỉnh thứ hai.

Mục đích là để có được một đồ thị, nơi mỗi đỉnh có một cạnh đến, và một cạnh để lại.

Answer 1

Chỉ cần tạo biểu đồ với các cạnh nối hai người nếu họ được phép chia sẻ quà tặng và sau đó sử dụng thuật toán khớp hoàn hảo. (Hãy tìm "Đường dẫn, Cây và Hoa" cho thuật toán (thông minh))

Answer 2

Tôi sẽ không sử dụng các ghép nối không được phép vì điều này làm tăng đáng kể độ phức tạp của sự cố. Chỉ cần nhập tên và địa chỉ của mọi người vào danh sách. Tạo một bản sao của danh sách và tiếp tục xáo trộn nó cho đến khi các địa chỉ trong mỗi vị trí của hai danh sách không khớp. Điều này sẽ đảm bảo rằng không ai có được bản thân, hoặc vợ/chồng của họ.

Là một phần thưởng, nếu bạn muốn thực hiện phong cách bầu cử bí mật này, in phong bì từ danh sách đầu tiên và tên từ danh sách thứ hai. Đừng nhìn trộm trong khi nhồi các phong bì. (Hoặc bạn chỉ có thể tự động gửi email cho mọi người mà họ chọn.)

Thậm chí còn có nhiều giải pháp cho vấn đề này trên this thread.

Answer 3

Hmmm. Tôi lấy một khóa học trong lý thuyết đồ thị, nhưng đơn giản hơn là chỉ ngẫu nhiên hoán đổi danh sách của bạn, ghép từng nhóm liên tiếp, sau đó hoán đổi bất kỳ phần tử nào không được phép với một phần tử khác. Vì không có người không được phép trong bất kỳ cặp đã cho nào, trao đổi sẽ luôn thành công nếu bạn không cho phép hoán đổi với nhóm được chọn. Thuật toán của bạn quá phức tạp.

Answer 4

Tôi đã tự làm điều này, cuối cùng thuật toán tôi đã sử dụng không mô hình chính xác việc vẽ tên ra khỏi mũ, nhưng khá gần chết tiệt. Về cơ bản trộn danh sách, sau đó ghép từng người với người tiếp theo trong danh sách. Sự khác biệt duy nhất với tên bản vẽ ngoài mũ là bạn nhận được một chu kỳ thay vì có khả năng nhận được các phân nhóm nhỏ của những người chỉ trao đổi quà tặng với nhau. Nếu bất cứ điều gì có thể là một tính năng.

thực hiện bằng Python:

import random 
from collections import deque 
def pairup(people): 
    """ Given a list of people, assign each one a secret santa partner 
    from the list and return the pairings as a dict. Implemented to always 
    create a perfect cycle""" 
    random.shuffle(people) 
    partners = deque(people) 
    partners.rotate() 
    return dict(zip(people,partners)) 

Answer 5

tôi vừa tạo ra một ứng dụng web mà sẽ thực hiện chính xác này - http://www.secretsantaswap.com/

thuật toán của tôi cho phép phân nhóm. Nó không đẹp, nhưng nó hoạt động.

Hoạt động như sau:
1. assign một định danh duy nhất cho tất cả những người tham gia, hãy nhớ mà nhóm họ đang ở
2. trùng lặp và shuffle danh sách đó (mục tiêu)
3. tạo một mảng các số của những người tham gia trong mỗi phân nhóm
4. mảng trùng lặp từ [3] cho các mục tiêu
5. tạo một mảng mới để giữ các kết quả cuối cùng
6. lặp lại thông qua người tham gia chỉ định mục tiêu đầu tiên không khớp với bất kỳ điều nào sau đây tiêu chí:
          A. tham gia == mục tiêu
          B. participant.Subgroup == target.Subgroup
          C. chọn mục tiêu sẽ gây ra một nhóm để thất bại trong tương lai (ví dụ nhóm 1 phải luôn luôn có ít nhất là nhiều người không phân nhóm 1 chỉ tiêu còn lại như những người tham gia nhóm 1 người tham gia còn lại)
          D. tham gia (n + 1) == mục tiêu (n +1)
Nếu chúng ta gán mục tiêu chúng tôi cũng giảm các mảng từ 3 và 4

Vì vậy, không đẹp (chút nào) nhưng nó hoạt động. Hy vọng nó sẽ giúp,

Dan Carlson

Answer 6

Tạo một đồ thị mà mỗi cạnh là "giftability" Đỉnh đại diện cho Vợ chồng sẽ KHÔNG được liền kề. Chọn một cạnh ngẫu nhiên (đó là một nhiệm vụ tặng quà). Xóa tất cả các cạnh đến từ giò và tất cả các cạnh sẽ chuyển tới người nhận và lặp lại.

Answer 7

Có một khái niệm trong lý thuyết đồ thị được gọi là Hamiltonian Circuit mô tả "mục tiêu" mà bạn mô tả. Một mẹo cho bất kỳ ai tìm thấy điều này là cho người dùng biết "hạt giống" nào được sử dụng để tạo biểu đồ. Bằng cách này, nếu bạn phải tạo lại đồ thị bạn có thể. "Hạt giống" cũng hữu ích nếu bạn phải thêm hoặc xóa một người. Trong trường hợp đó, chỉ cần chọn "hạt giống" mới và tạo biểu đồ mới, đảm bảo cho người tham gia biết "hạt giống" là "hạt giống" mới nhất.

Answer 8

Đây là một cách thực hiện đơn giản trong java cho vấn đề santa bí mật.

public static void main(String[] args) { 
    ArrayList<String> donor = new ArrayList<String>(); 
    donor.add("Micha"); 
    donor.add("Christoph"); 
    donor.add("Benj"); 
    donor.add("Andi"); 
    donor.add("Test"); 
    ArrayList<String> receiver = (ArrayList<String>) donor.clone(); 

    Collections.shuffle(donor); 
    for (int i = 0; i < donor.size(); i++) { 
     Collections.shuffle(receiver); 
     int target = 0; 
     if(receiver.get(target).equals(donor.get(i))){    
      target++; 
     }   
     System.out.println(donor.get(i) + " => " + receiver.get(target)); 
     receiver.remove(receiver.get(target)); 
    } 
} 

Answer 9

Giải pháp Python tại đây.

Cho một chuỗi (person, tags), trong đó thẻ tự nó là chuỗi (có thể trống), thuật toán của tôi gợi ý một chuỗi người mà mỗi người tặng quà cho chuỗi tiếp theo trong chuỗi (người cuối cùng được ghép nối với cái đầu tiên).

Các thẻ tồn tại để mọi người có thể được nhóm lại và mỗi lần người tiếp theo được chọn từ nhóm không tham gia nhiều nhất với người cuối cùng được chọn. Người đầu tiên được chọn bởi một bộ thẻ trống, vì vậy nó sẽ được chọn từ nhóm dài nhất.

Vì vậy, với một chuỗi đầu vào của:

example_sequence= [ 
    ("person1", ("male", "company1")), 
    ("person2", ("female", "company2")), 
    ("person3", ("male", "company1")), 
    ("husband1", ("male", "company2", "marriage1")), 
    ("wife1", ("female", "company1", "marriage1")), 
    ("husband2", ("male", "company3", "marriage2")), 
    ("wife2", ("female", "company2", "marriage2")), 
] 

một gợi ý là:

[ 'PERSON1 [nam, company1]', 'viên2 [nữ, company2]', 'person3 [nam, công ty1] ', ' vợ2 [nữ, hôn nhân2, công ty2] ', ' chồng1 [nam, hôn nhân1, công ty2] ', ' chồng2 [nam, hôn nhân2, công ty3] ', ' wife1 [nữ, hôn nhân1 , company1] ']

Tất nhiên, nếu tất cả mọi người không có thẻ (ví dụ: một tuple trống) sau đó chỉ có một nhóm để lựa chọn.

Không phải lúc nào cũng có giải pháp tối ưu (nghĩ chuỗi đầu vào gồm 10 phụ nữ và 2 nam giới, thể loại của họ là thẻ duy nhất được cung cấp), nhưng nó hoạt động tốt nhất có thể.

Tương thích Py2/3.

import random, collections 

class Statistics(object): 
    def __init__(self): 
     self.tags = collections.defaultdict(int) 

    def account(self, tags): 
     for tag in tags: 
      self.tags[tag] += 1 

    def tags_value(self, tags): 
     return sum(1./self.tags[tag] for tag in tags) 

    def most_disjoined(self, tags, groups): 
     return max(
      groups.items(), 
      key=lambda kv: (
       -self.tags_value(kv[0] & tags), 
       len(kv[1]), 
       self.tags_value(tags - kv[0]) - self.tags_value(kv[0] - tags), 
      ) 
     ) 

def secret_santa(people_and_their_tags): 
    """Secret santa algorithm. 

    The lottery function expects a sequence of: 
    (name, tags) 

    For example: 

    [ 
     ("person1", ("male", "company1")), 
     ("person2", ("female", "company2")), 
     ("person3", ("male", "company1")), 
     ("husband1", ("male", "company2", "marriage1")), 
     ("wife1", ("female", "company1", "marriage1")), 
     ("husband2", ("male", "company3", "marriage2")), 
     ("wife2", ("female", "company2", "marriage2")), 
    ] 

    husband1 is married to wife1 as seen by the common marriage1 tag 
    person1, person3 and wife1 work at the same company. 
    … 

    The algorithm will try to match people with the least common characteristics 
    between them, to maximize entrop— ehm, mingling! 

    Have fun.""" 

    # let's split the persons into groups 

    groups = collections.defaultdict(list) 
    stats = Statistics() 

    for person, tags in people_and_their_tags: 
     tags = frozenset(tag.lower() for tag in tags) 
     stats.account(tags) 
     person= "%s [%s]" % (person, ",".join(tags)) 
     groups[tags].append(person) 

    # shuffle all lists 
    for group in groups.values(): 
     random.shuffle(group) 

    output_chain = [] 
    prev_tags = frozenset() 
    while 1: 
     next_tags, next_group = stats.most_disjoined(prev_tags, groups) 
     output_chain.append(next_group.pop()) 
     if not next_group: # it just got empty 
      del groups[next_tags] 
      if not groups: break 
     prev_tags = next_tags 

    return output_chain 

if __name__ == "__main__": 
    example_sequence = [ 
     ("person1", ("male", "company1")), 
     ("person2", ("female", "company2")), 
     ("person3", ("male", "company1")), 
     ("husband1", ("male", "company2", "marriage1")), 
     ("wife1", ("female", "company1", "marriage1")), 
     ("husband2", ("male", "company3", "marriage2")), 
     ("wife2", ("female", "company2", "marriage2")), 
    ] 
    print("suggested chain (each person gives present to next person)") 
    import pprint 
    pprint.pprint(secret_santa(example_sequence))