गुप्त सांता - 'वैध' क्रमपरिवर्तन उत्पन्न करना

Question

मेरे दोस्तों ने मुझे गुप्त सांता के खेल खेलने के लिए घर आमंत्रित किया, जहां हमें बहुत सारे & समूह में किसी मित्र के लिए 'सांता' की भूमिका निभाते हैं।

तो, हम अपने सभी नाम लिखते हैं और नाम यादृच्छिक रूप से चुनते हैं। यदि हम में से कोई भी अपना नाम उठाकर समाप्त होता है, तो हम फिर से नाम बदलते हैं और नाम चुनते हैं (तर्क यह है कि कोई व्यक्ति स्वयं का सांता नहीं हो सकता है)।

खेलते समय हम में से सात हैं इसलिए मैंने कुछ प्रतिबंधों के साथ (1: 7) के क्रमपरिवर्तन के रूप में अंतिम 'सांता-आवंटन' के बारे में सोचा।

मैं कैसे हम विशेष रूप से या किसी भी प्रोग्रामिंग भाषा या यहां तक ​​कि एक एल्गोरिथ्म में मेथेमेटिका इस्तेमाल कर सकते हैं के बारे में विभिन्न विचारों आमंत्रित करना चाहते हैं:

• सूची/प्रिंट आउट सभी 'वैध' सांता-आवंटन
• के रूप में 'गुप्त सांता' खेल रहे हैं दोस्तों की संख्या बढ़ती है

Answer 1

मैं इस प्रस्ताव:

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}}

यह हीके के समारोह की तुलना में काफी तेज है।

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

{0.483, Null}

{1.482, Null}

कोड की पारदर्शिता की अनदेखी करते हुए कई बार तेजी से अभी भी बनाया जा सकता है:

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

f2[9]; //Timing 

{0.162, Null}

Answer 2

मेथेमेटिका में आप

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

की तरह कुछ कर सकता है स्केलेबल है

जहां n पूल में लोगों की संख्या है। तो उदाहरण के लिए secretSanta[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}} 

संपादित

यह मेथेमेटिका में Combinatorica पैकेज की तरह दिखता है वास्तव में, एक Derangements कार्य है ताकि आप भी तरह

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

हालांकि पर कुछ कर सकते हैं मेरे सिस्टम Derangements[Range[n]] ऊपर दिए गए फ़ंक्शन की तुलना में एक कारक 2 धीमा है।

Answer 3

जो आप खोज रहे हैं उसे derangement (एक और प्यारा लेटिनेट शब्द पता है, जैसे exsanguination और defenestration) कहा जाता है।

सभी क्रमिक क्रमों का अंश 1/ई = लगभग 36.8% तक पहुंचता है - इसलिए यदि आप यादृच्छिक क्रमपरिवर्तन उत्पन्न कर रहे हैं, तो बस उन्हें उत्पन्न करते रहें, और एक बहुत अधिक संभावना है कि आपको 5 में से कोई एक मिलेगा या एक यादृच्छिक क्रमपरिवर्तन के 10 चयन।

This presentation बहुत नीचे करने वाली पृथ्वी है (10.1% एक 5 के भीतर यादृच्छिक क्रमपरिवर्तन, हर अतिरिक्त 5 क्रमपरिवर्तन नहीं मिल की संभावना 10 का एक और पहलू से एक गड़बड़ी नहीं मिल की संभावना को कम करती है) और पैदा करने के लिए पुनरावर्ती एल्गोरिदम देता है क्रमिकता को अस्वीकार करने के बजाय सीधे अपमान, जो अपमान नहीं हैं।

Answer 4

एक क्रमपरिवर्तन जो स्वयं के लिए कोई तत्व नहीं है derangement है। चूंकि एन बढ़ता है, अपमान का अंश स्थिर 1/ई तक पहुंचता है। इस तरह, यह यादृच्छिक रूप से क्रमपरिवर्तन चुनते समय, (औसत पर) लेता है और एक अपमान प्राप्त करने का प्रयास करता है।

विकिपीडिया आलेख में छोटे एन के लिए स्पष्ट मानों की गणना करने के लिए अभिव्यक्तियां शामिल हैं।

Answer 5

मैं निर्मित दस्तावेज में Subfactorial समारोह और में आए उदाहरण के लिए उदाहरणों में से एक को बदल दिया:

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

कोई फ़ंक्शन देखने के लिए Subfactorial का उपयोग कर सकता है।

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

Mr.Wizard के जवाब के रूप में, मैं teleSecretSanta SparseArray के माध्यम से अनुकूलित किया जा सकता है पर शक। हालांकि, इस तरह के शेंगेनियों का प्रयास करने के लिए मैं इस समय बहुत नशे में हूं। (मजाक कर रहा हूँ ... मैं वास्तव में बहुत आलसी और बेवकूफ हूं।)

Answer 6

यह मान्य अपमानों की गिनती के बारे में आपके प्रश्न का उत्तर नहीं देता है, लेकिन यह निम्नलिखित के साथ एक उत्पन्न करने के लिए एक एल्गोरिदम देता है (जो आप चाहते हैं) गुण:

1. यह guaranties सांता संबंध में एक भी चक्र है कि वहाँ (यदि आप 4 में खेलते हैं, आप 2 सांता जोड़ों के साथ अंत नहीं है -> 2 चक्र),
2. तो यह और भी साथ कुशलता से काम करता है प्लेयर की बहुत बड़ी संख्या,
3. यदि उचित रूप से लागू किया गया है, तो कोई भी नहीं जानता कि किसका सांता,
4. इसे कंप्यूटर की आवश्यकता नहीं है, केवल कुछ पेपर।

यहाँ एल्गोरिथ्म:

• हर खिलाड़ी को एक लिफाफे पर उसे/उसके नाम लिखते हैं और एक मुड़ा हुआ कागज में उसके/उसका नाम डालता लिफाफे में।
• एक भरोसेमंद खिलाड़ी (उपरोक्त संपत्ति # 3 के लिए) सभी लिफाफे लेता है और उन्हें अपनी पिछली तरफ देखता है (जहां कोई नाम लिखा नहीं जाता है)।
• एक बार लिफाफे काफी अच्छी तरह से घुमाए जाते हैं, हमेशा पीछे की ओर देखते हैं, भरोसेमंद खिलाड़ी पेपर को प्रत्येक लिफाफे में निम्नलिखित में ले जाता है।
• लिफाफे को फिर से घुमाने के बाद, लिफाफे उस खिलाड़ी को वापस वितरित किए जाते हैं जिसका नाम उनके ऊपर है, और प्रत्येक खिलाड़ी उस व्यक्ति का सांता है जिसका नाम लिफाफा में है।