प्रत्येक इंडेक्स

Question

पर अद्वितीय मानों के साथ संख्याओं के एकाधिक अनुक्रम उत्पन्न करें मेरे पास 1:n संख्याओं के साथ एक पंक्ति है। मैं संख्या के साथ भी एक दूसरे पंक्ति जोड़ने के लिए देख रहा हूँ 1:n लेकिन इन एक यादृच्छिक क्रम में होना चाहिए, जबकि संतोषजनक निम्नलिखित:

1. कोई स्थिति है दोनों पंक्तियों में एक ही नंबर
2. संख्या का कोई संयोजन होता है दो बार

उदाहरण के लिए, में निम्नलिखित

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 6 15 8 13 12 7 ... 

संख्या 7 दोनों पंक्तियों 1 और 2 में एक ही स्थान पर होता है (अर्थात् स्थिति 7; जिससे शासन 1)

संतोषजनक नहीं निम्नलिखित

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 7 15 8 13 12 2 ... 

2 + 7 के संयोजन में प्रकट होता है, जबकि दो बार (पदों 2 और 7 में, जिससे नियम 2 संतोषजनक नहीं)।

यह संभवतः संभव होगा - लेकिन अनावश्यक रूप से समय लेने वाली - हाथ से ऐसा करने के लिए (कम से कम एक उचित संख्या तक), लेकिन MATLAB में इसके लिए काफी सुंदर समाधान होना चाहिए।

Answer 1

यह काफी सरल है।नोड्स का एक यादृच्छिक क्रमपरिवर्तन बनाएं, लेकिन निम्नानुसार सूची की व्याख्या करें: इसे नोड्स के चारों ओर एक यादृच्छिक चलने के रूप में व्याख्या करें, और यदि नोड 'बी' नोड 'ए' के ​​बाद प्रकट होता है, तो इसका मतलब है कि नोड 'बी' नोड के नीचे दिखाई देता है ' सूचियों में:

तो अगर अपने प्रारंभिक यादृच्छिक क्रमपरिवर्तन

3 2 5 1 4 

फिर इस मामले में टहलने के 3 -> 2 -> 5 -> 1 -> 4 है और इस प्रकार आप पंक्तियों बनाता है:

Row 1: 1 2 3 4 5 
Row 2: 4 5 2 3 1 

यह यादृच्छिक चलते हैं दोनों स्थितियों को संतुष्ट करें।

लेकिन क्या आप अपने नेटवर्क में एक से अधिक चक्रों की अनुमति देना चाहते हैं? मुझे पता है कि आप नहीं चाहते कि दो लोगों को एक-दूसरे की टोपी हो। लेकिन 7 लोगों के बारे में क्या, उनमें से एक दूसरे के टोपी हैं और अन्य एक-दूसरे के टोपी हैं? क्या यह स्वीकार्य और/या वांछनीय है?

Answer 2

इस समस्या को क्रमपरिवर्तन के व्यंग्य कहा जाता है।
अपने डेटा का यादृच्छिक क्रमपरिवर्तन खोजने के लिए, रैन्डपर्म फ़ंक्शन का उपयोग करें।

x = [1 2 3 4 5 6 7]; 
y = randperm(x); 

फिर, आप जांच सकते हैं कि अनुक्रम कानूनी है। यदि नहीं, तो इसे बार-बार करें ..
आपके पास probability लगभग 0.3 बार सफल होने के लिए है, जिसका अर्थ है कि आपको इसे खोजने तक लगभग 10/3 बार प्रयास करने की आवश्यकता है। इसलिए आपको वास्तव में उत्तर मिल जाएगा।

वैकल्पिक रूप से, आप एक यादृच्छिक अपमान बनाने के लिए this algorithm का उपयोग कर सकते हैं।

संपादित

आप आकार> 2 का ही चक्र चाहते हैं, इस समस्या का सामान्यीकरण है। इसमें लिखा गया है कि that case में छोटा है, लेकिन इसे निश्चित चरणों में खोजने के लिए काफी बड़ा है। तो एक ही दृष्टिकोण अभी भी मान्य है।

Answer 3

एंड्री ने आपको पहले से ही randperm और अस्वीकृति-नमूना-जैसी दृष्टिकोण की ओर इशारा किया है। क्रमपरिवर्तन p उत्पन्न करने के बाद, यह निर्धारित करने का एक आसान तरीका है कि उसके पास निश्चित बिंदु है any(p==1:n) है। यह जांचने का एक आसान तरीका है कि इसमें लंबाई 2 के चक्र होते हैं any(p(p)==1:n) है।

तो यह क्रमपरिवर्तन 1:n की p अपने आवश्यकताओं को पूरा करने हो जाता है:

p=[]; 
while (isempty(p)) 
    p=randperm(n); 
    if any(p==1:n), p=[]; 
    elseif any(p(p)==1:n), p=[]; 
    end 
end 

एक for पाश के साथ और प्रत्येक गिनती while पाश की पुनरावृत्तियों के लिए इस आसपास, ऐसा लगता है एक औसत 4.5 क्रमपरिवर्तन पर उत्पन्न करने के लिए की जरूरत है प्रत्येक "वैध" एक (और 6.2 के लिए यदि लंबाई तीन के चक्रों की अनुमति नहीं है, तो)। बहुत ही रोचक।