Bí mật ở Santa - Tạo các hoán vị 'hợp lệ'

Question

Bạn bè của tôi mời tôi về nhà chơi trò chơi Bí mật ở Santa, nơi chúng tôi phải vẽ rất nhiều & đóng vai trò 'Santa' cho một người bạn trong nhóm.

Vì vậy, chúng tôi viết tất cả tên và chọn tên ngẫu nhiên. Nếu bất kỳ ai trong chúng ta kết thúc có tên riêng của họ được chọn, sau đó chúng tôi cải tổ lại và chọn tên tất cả hơn một lần nữa (lý do là một trong những không thể là Santa của riêng mình).

Có bảy người trong chúng tôi trong khi chơi nên tôi nghĩ về "phân bổ Santa" cuối cùng như một hoán vị (1: 7) trên chính nó, với một số hạn chế.

tôi trân trọng kính mời những ý tưởng khác nhau về cách chúng tôi có thể sử dụng Mathematica đặc biệt hoặc bất kỳ ngôn ngữ lập trình hay thậm chí là một thuật toán để:

• Danh sách/in ra tất cả các ông già Noel-phân bổ 'hợp lệ'
• là khả năng mở rộng như số lượng bạn bè chơi 'bí mật ông già Noel' mọc

Answer 1

Tôi đề nghị này:

f[s_List] := Pick[#, Inner[SameQ, #, s, Nor]] & @ Permutations@s 

f @ Range @ 4 

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2}, 
{3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

Đây là nhanh hơn so với chức năng Heike của đáng kể.

f @ Range @ 9; //Timing 
secretSanta[9]; //Timing 

{0.483, Null}

{1.482, Null}

Bỏ qua sự minh bạch mã, điều này có thể được thực hiện nhanh hơn nhiều lần vẫn:

f2[n_Integer] := With[{s = Range@n}, 
    # ~Extract~ 
     SparseArray[Times@@BitXor[s, #] & /@ #]["NonzeroPositions"] & @ Permutations@s 
    ] 

f2[9]; //Timing 

{0.162, Null}

Answer 2

trong Mathematica bạn có thể làm một cái gì đó giống như

secretSanta[n_] := 
    DeleteCases[Permutations[Range[n]], a_ /; Count[a - Range[n], 0] > 0] 

trong đó n là số người trong hồ bơi. Sau đó, ví dụ secretSanta[4] lợi nhuận

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2}, 
    {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}} 

Sửa

Dường như Combinatorica gói trong Mathematica thực sự có một chức năng Derangements, vì vậy bạn cũng có thể làm một cái gì đó giống như

Needs["Combinatorica`"] 
Derangements[Range[n]] 

mặc dù trên của tôi hệ thống Derangements[Range[n]] chậm hơn khoảng 2 lần so với hàm trên.

Answer 3

Những gì bạn đang tìm kiếm được gọi là derangement (một từ Latinh đáng yêu khác cần biết, như exsanguination và defenestration).

Phần nhỏ của tất cả hoán vị là phương pháp tiếp cận 1/e = xấp xỉ 36,8% - vì vậy nếu bạn đang tạo các hoán vị ngẫu nhiên, chỉ cần tiếp tục tạo chúng, và có xác suất rất cao mà bạn sẽ tìm thấy một trong 5 hoặc 10 lựa chọn của một hoán vị ngẫu nhiên. (10,1% cơ hội không tìm thấy một trong 5 hoán vị ngẫu nhiên, mỗi 5 hoán vị bổ sung làm giảm cơ hội không tìm thấy một sự xáo trộn bởi một yếu tố khác là 10)

This presentation là khá down-to-earth và đưa ra một thuật toán đệ quy để tạo ra trực tiếp, thay vì phải từ chối hoán vị mà không phải là sự quấy rầy.

Answer 4

Một hoán vị không ánh xạ thành phần nào cho chính nó là derangement. Khi n tăng, phần thập phân của phương trình tiếp cận hằng số 1/e. Như vậy, phải mất (trung bình) e cố gắng để có được một derangement, nếu chọn một hoán vị một cách ngẫu nhiên.

Bài viết wikipedia bao gồm các biểu thức để tính giá trị rõ ràng cho n nhỏ.

Answer 5

tôi tình cờ được xây dựng trong Subfactorial chức năng trong tài liệu và đã thay đổi một trong các ví dụ để sản xuất:

Remove[teleSecretSanta]; 
teleSecretSanta[dims_Integer] := 
With[{spec = Range[dims]}, 
    With[{ 
    perms = Permutations[spec], 
    casesToDelete = DiagonalMatrix[spec] /. {0 -> _}}, 
    DeleteCases[perms, Alternatives @@ casesToDelete] 
    ] 
    ] 

Người dùng có thể sử dụng Subfactorial để kiểm tra chức năng.

Length[teleSecretSanta[4]] == Subfactorial[4] 

Như câu trả lời của Mr.Wizard, tôi nghi ngờ teleSecretSanta có thể được tối ưu hóa thông qua SparseArray. Tuy nhiên, tôi quá say tại thời điểm này để cố gắng như vậy shenanigans. (đùa ... Tôi thực sự quá lười biếng và ngu ngốc.)

Answer 6

Điều này không trả lời câu hỏi của bạn về cách tính các chuyển đổi hợp lệ, nhưng nó cung cấp thuật toán để tạo một (có thể là những gì bạn muốn). thuộc tính:

1. nó guaranties rằng có một chu trình đơn trong mối quan hệ của ông già Noel (nếu bạn chơi ở 4, bạn không kết thúc với 2 ông già Noel cặp vợ chồng -> 2 chu kỳ),
2. nó hoạt động một cách hiệu quả ngay cả với số lượng người chơi rất lớn,
3. nếu được áp dụng công bằng, không ai biết ai là người của ông già Noel,
4. nó không cần một máy tính, chỉ có một số giấy.

Đây là thuật toán:

• Mỗi người chơi viết của mình/tên của mình vào một phong bì và đưa cô/tên của mình trong một bài báo gấp trong phong bì.
• Một trình phát đáng tin cậy (đối với thuộc tính số 3 ở trên) lấy tất cả các phong bì và xáo trộn chúng nhìn vào mặt sau của chúng (nơi không có tên được viết).
• Khi phong bì được xáo trộn đủ tốt, luôn nhìn vào mặt sau, trình phát tin cậy sẽ di chuyển giấy trong mỗi phong bì sang phong bì sau.
• Sau khi xáo trộn phong bì một lần nữa, phong bì được phân phát lại cho người chơi có tên trên đó, và mỗi người chơi là ông già Noel của người có tên trong phong bì.