बेतरतीब ढंग से एक सरणी

Question

की अनूठी सबसेट नमूने अगर मैं एक सरणी है:

a = [1,2,3] 

मैं कैसे सरणी के बेतरतीब ढंग से चयन सबसेट, ऐसी है कि प्रत्येक सबसेट के तत्वों अद्वितीय हैं करते हैं? यही कारण है, a के लिए संभव सबसेट होगा:

[] 
[1] 
[2] 
[3] 
[1,2] 
[2,3] 
[1,2,3] 

मैं संभव सबसेट के सभी उत्पन्न नहीं कर सकते के रूप में एक के वास्तविक आकार तो वहाँ कई, कई सबसेट हैं बहुत बड़ा है। फिलहाल, मैं 'यादृच्छिक चलना' विचार का उपयोग कर रहा हूं - एक के प्रत्येक तत्व के लिए, मैं 'सिक्का फिसलता हूं' और सिक्का ऊपर आने पर इसे शामिल करता है - लेकिन मुझे यकीन नहीं है कि यह वास्तव में अंतरिक्ष को समान रूप से नमूना देता है या नहीं। यह लगता है जैसे यह मध्य की ओर पूर्वाग्रह करता है, लेकिन यह मेरा दिमाग पैटर्न-मिलान कर सकता है, क्योंकि अधिक मध्यम आकार की संभावनाएं होंगी।

क्या मैं सही दृष्टिकोण का उपयोग कर रहा हूं, या मुझे यादृच्छिक रूप से नमूना कैसे करना चाहिए?

(मुझे पता है कि यह एक भाषा नास्तिक और 'mathsy' प्रश्न के और अधिक है, लेकिन मुझे लगा कि यह वास्तव में Mathoverflow सामग्री नहीं था -। मैं सिर्फ एक व्यावहारिक जवाब की जरूरत है)

Answer 1

आप यादृच्छिक संख्या उत्पन्न कर सकता है

class Array 
    def random_subset(n=1) 
    raise ArgumentError, "negative argument" if n < 0 
    (1..n).map do 
     r = rand(2**self.size) 
     self.select.with_index { |el, i| r[i] == 1 } 
    end 
    end 
end 

उपयोग::

a.random_subset(3) 
#=> [[3, 6, 9], [4, 5, 7, 8, 10], [1, 2, 3, 4, 6, 9]] 

, उन्हें बाइनरी में बदल जाएंगे और अपने मूल सरणी जहां बिट्स यहाँ थे 1. से तत्वों का चयन Array वर्ग के लिए एक बंदर-पैच के रूप में इस का कार्यान्वयन है 210

आम तौर पर यह इतना बुरा नहीं करता है, यह ओ (एन * एम) है जहां n आप चाहते हैं कि subsets की संख्या है और एम सरणी की लंबाई है।

Answer 2

a.select {|element| rand(2) == 0 } 

प्रत्येक तत्व के लिए, एक सिक्का फ़्लिप किया जाता है। यदि सिर (== 0), तो यह चुना जाता है।

Answer 3

मुझे लगता है कि सिक्का फ़्लिपिंग ठीक है।

ar = ('a'..'j').to_a 
p ar.select{ rand(2) == 0 } 

एक सरणी 10 तत्वों के साथ 2 ** 10 संभव संयोजनों (सहित [] और सभी 10 तत्वों) जो अधिक तो 10 बार (1 या 0) कुछ भी नहीं है। यह चार, पांच और छह तत्वों के अधिक सरणी आउटपुट करता है, क्योंकि पावरसेट में बहुत अधिक लोग हैं।

Answer 4

बस अपने मूल "सिक्का फ़्लिपिंग" विचार के साथ आगे बढ़ें। यह समान रूप से संभावनाओं की जगह का नमूना देता है।

ऐसा लगता है कि यह "मध्य" की ओर पक्षपातपूर्ण है, लेकिन ऐसा इसलिए है क्योंकि "मध्य" में संभावनाओं की संख्या सबसे बड़ी है। इसके बारे में सोचें: कोई तत्व नहीं है, और केवल तत्वों के साथ केवल 1 संभावना है। 1 तत्व के साथ एन संभावनाएं हैं, और एन संभावनाएं (एन -1) तत्वों के साथ हैं। चूंकि चुने गए तत्वों की संख्या (एन/2) के करीब हो जाती है, संभावनाओं की संख्या बहुत तेजी से बढ़ती है।

Answer 5

शक्ति सेट से एक यादृच्छिक तत्व का चयन करने के लिए एक रास्ता है निम्नलिखित:

my_array = ('a'..'z').to_a 
power_set_size = 2 ** my_array.length 
random_subset = rand(power_set_size) 
subset = [] 
random_subset.to_i(2).chars.each_with_index do |bit, corresponding_element| 
    subset << my_array[corresponding_element] if bit == "1" 
end 

यह बजाय बस अपना सुविधा के लिए असली "बिट्स" और बिटवाइज़ संचालन के साथ काम करने से तार कार्यों का उपयोग करता है। आप वास्तविक बिट्स का उपयोग कर इसे तेज (मुझे लगता है) एल्गोरिदम में बदल सकते हैं।

यह क्या करता है, 0 और 2 ** array.length बीच का एक पूर्णांक के रूप में array की Powerset एन्कोड करने के लिए है और फिर यादृच्छिक पर उन पूर्णांक में से एक (समान रूप से यादृच्छिक, वास्तव में) उठाता है। फिर यह बिटमैस्क (0 = तत्व सबसेट में है, 0 = यह नहीं है) का उपयोग कर array के किसी विशेष सबसेट में पूर्णांक को डीकोड करता है।

इस तरह आपके पास अपने सरणी के पावर सेट पर एक समान वितरण है।