एल्गोरिथ्म छंटाई बराबर मान रखने के लिए अलग

Question

मनोविज्ञान प्रयोगों अक्सर आप की आवश्यकता छद्म randomize करने के लिए परीक्षण आदेश, ताकि परीक्षणों जाहिरा तौर पर यादृच्छिक हैं, लेकिन आप भी इसी तरह के कई परीक्षणों लगातार नहीं मिलता है (जो एक विशुद्ध रूप से यादृच्छिक साथ भी हो सकता है आदेश)।

मान लीजिए कि प्रत्येक परीक्षण पर दृश्य प्रदर्शन एक रंग और एक आकार की है कि दो:

display_list = [] 
colours = {0: 'red', 1: 'blue', 2: 'green', 3: 'yellow'} 
sizes = [1] * 20 + [2] * 20 + [3] * 20 + [4] * 20 + [5] * 20 + [6] * 20 
for i in range(120): 
    display_list.append({'colour': colours[i % 4], 'size': sizes[i]}) 
print(display_list) 

और हम या तो संपत्ति इस समारोह का उपयोग कर के लिए समान मान है कि लगातार परीक्षणों की अधिकतम संख्या देख सकते हैं:

def consecutive_properties(seq, field): 
    longest_run = 0 
    prev_value = None 
    current_run = 0 
    for d in seq: 
     if d[field] == prev_value: 
      current_run += 1 
     else: 
      current_run = 1 
     if current_run > longest_run: 
      longest_run = current_run 
     prev_value = d[field] 
    return longest_run 

आउटपुट:

>>> print("Consecutive colours: ", consecutive_properties(display_list, 'colour') 
('Consecutive colours: ', 1) 

>>> print("Consecutive sizes: ", consecutive_properties(display_list, 'size')) 
('Consecutive sizes: ', 20) 

वहाँ किसी भी एल्गोरिदम हैं आप जानते हैं कि या तो दोनों या दोनों गुणों के लगातार रन को कम करने की अनुमति होगी, या कम से कम इन रनों को निर्दिष्ट लंबाई से नीचे रखें? यदि उत्तरार्द्ध, चलो एक ही रंग या आकार की पंक्ति में 4 से अधिक नहीं कहें।

---

मैं क्या कोशिश की है:

समाधान मैं अब मूल रूप से एक से थोड़ा बुद्धिमान bogosort, जो बुरी तरह अक्षम हो गया है है। मूल रूप से:

• आप गुण के सभी क्रमपरिवर्तन युक्त टुकड़ों में पूरी सूची को तोड़ने: यदि आप लंबाई 24 के टुकड़ों में display_list टूट, प्रत्येक टुकड़ा प्रत्येक रंग प्रत्येक आकार के साथ रखा गया है। मान लेते हैं कि परीक्षण सूची हमेशा इन क्रमचय टुकड़ों में विभाजित किया जा सकता है, क्योंकि आप जानते हैं कि क्रमपरिवर्तन प्रयोग के डिजाइन से हैं करते हैं।
• आप अधिकतम रन लंबाई प्रति चंक
• चुनते हैं जब तक कि प्रत्येक खंड के लिए रन लम्बाई अधिकतम मूल्य से कम न हो जाए (वास्तव में इसका मतलब है कि समग्र परीक्षण सूची में, आपके रन लंबाई की दोगुनी हो सकती हैं, क्योंकि आप एक खंड के अंत में और अगले की शुरुआत में इस लंबाई का एक रन चला सकते हैं)

Answer 1

प्रश्न: कर रहे हैं वहाँ किसी भी एल्गोरिदम आपको लगता है कि के बारे में पता एक या दोनों संपत्तियों की लगातार रन कम से कम की अनुमति होगी, या कम से कम एक निर्दिष्ट लंबाई नीचे इन रन रहते हैं?

हां। यदि यह पहले से ही चल रहा है तो रंग या आकार की संभावना को कम करके इसे करने के लिए ऐसा करने के लिए एक आसान एल्गोरिदम है।

from random import randrange 

def choose(colors, numselections, maxrun): 
    'Repeatedly choose colors. Gradually reduce selection probability to avoid runs.' 
    colors = list(colors) 
    n = len(colors) 
    total = n * maxrun 
    current_run = 0 
    for _ in range(numselections): 
     i = randrange(total - current_run) // maxrun 
     yield colors[i] 
     colors[i], colors[-1] = colors[-1], colors[i] 
     current_run = current_run + 1 if i==n-1 else 1 

if __name__ == '__main__': 
    colors = ['red', 'blue', 'green', 'yellow'] 
    for color in choose(colors, 100, maxrun=4): 
     print color 

नोट, इस दृष्टिकोण को अन्य उत्तरों की तुलना में कम प्रयास की आवश्यकता है जो रन से बचने के लिए शोधन तकनीकों का उपयोग करते हैं। साथ ही, ध्यान दें कि रन दूसरे शब्दों में एक बार में धीरे-धीरे फीका हुआ है।

Answer 2

क्षमा करें, यह कोई जवाब नहीं है, लेकिन टिप्पणियों में कोड पोस्ट करना मुश्किल है। यहाँ एक आसान तरीका consecutive_properties समारोह लिखना है

from operator import itemgetter 
from itertools import groupby 
def consecutive_properties(seq, field): 
    return max(sum(1 for x in g) for k,g in groupby(seq, key=itemgetter(field))) 

जब मैं समझता हूँ कि आपके सवाल का ठीक से मैं एक जवाब :)

Answer 3

में इस बारी करने के आप स्पष्ट रूप से सच अनियमितता की तरह कुछ के साथ संबंध नहीं कर रहे हैं की कोशिश करेंगे , यदि आप एक दूरी मीट्रिक परिभाषित करते हैं, और बेतरतीब ढंग से अपने अनुक्रम आकर्षित हां, तो आप किसी भी नए ड्रा अगर यह दूरी है "बहुत करीब" पिछले बराबरी पर है अस्वीकार कर सकते हैं, और बस फिर से आकर्षित।

आप एक परिमित सेट से ड्राइंग कर रहे हैं (जैसे कि, ताश का एक पैक) तो पूरे सेट ड्रा ढेर हो सकता है, और अपने तरह दो तत्वों गमागमन जब एक करीबी जोड़ी पाया जाता है शामिल होंगे, लेकिन अगर स्वैप तत्व अस्वीकार्य हो जाता है तो एक स्वैप पार्टनर को भी अस्वीकार कर दें, इसलिए प्रत्येक स्वैप चरण पूरे सेट में सुधार करता है।

आपके मानदंड भी संतुष्ट करने के लिए मुश्किल नहीं कर रहे हैं, यह बहुत जल्दी समाप्त कर देगा।

Answer 4

ddyer के रूप में कहा, तुम अनियमितता के बजाय छँटाई में रुचि रखते हैं।मेरे यहाँ समाधान होगा:

1. अपने स्रोत सूची
2. से एक यादृच्छिक एक तत्व उठाओ स्थिति मैं डेस्ट को पर अपने गंतव्य सूची
3. सम्मिलित एक से एक यादृच्छिक स्थिति मैं उठाओ। सूची
4. जांचें कि गंतव्य सूची मान्य है या नहीं। यदि नहीं, तो पहले वाली स्थिति बहाल करने और दोहराने

एक कार्य टुकड़ा:

from random import randint 
from operator import itemgetter 
from itertools import islice 

def reshuffle(_items, max_consequent): 
    items = _items[:] 
    new_order = [] 
    while items: 
     src_pos = randint(0, len(items)-1) 
     dest_pos = randint(0, len(new_order)) 
     item = items[src_pos] 
     new_order.insert(dest_pos, item) 
     if is_new_order_fine(new_order, max_consequent): 
      items.pop(src_pos) 
     else: 
      new_order.pop(dest_pos) 
    return new_order 

def is_new_order_fine(items, n_max): 
    return (
     not has_consecutive_keys(items, n_max, key=itemgetter('colour')) and 
     not has_consecutive_keys(items, n_max, key=itemgetter('size'))) 

# can be optimised - don't check all items, just surrounding N 
def has_consecutive_keys(items, n_max, key): 
    _has_n_keys = False 
    if len(items) >= n_max: 
     last_value = key(items[0]) 
     n_consequent = 1 
     for item in items[1:]: # can optimize by using iterator 
      if key(item) == last_value: 
       n_consequent += 1 
      else: 
       last_value = key(item) 
       n_consequent = 1 
      if n_consequent >= n_max: 
       _has_n_keys = True 
       break 
    return _has_n_keys 

ध्यान दें कि आप हर बार गंतव्य सूची में सभी आइटम की जाँच करने की जरूरत नहीं है, बाईं और दाईं तरफ कश्मीर

• : डाला नया आइटम (स्निपेट में लागू नहीं)

  संपादित चारों ओर आप has_consecutive_keys में groupby उपयोग कर सकते हैं (लेकिन छँटाई के बिना!)

Answer 5

लगातार तत्वों की संभावना बहुत अधिक नहीं है (अपने उदाहरण के रूप में), तो मैं बस फेरबदल होगा अगर शर्त पूरी नहीं है। जैसा कि आप देख सकते हैं, अधिकांश समय आप एक कोशिश से दूर हो जाते हैं, इसलिए यह काफी कुशल है।

In [1]: from random import shuffle 

In [2]: from itertools import groupby 

In [3]: from collections import Counter 

In [4]: def pseudo_shuffle(lst, limit, tries=1): 
    ...:  temp = list(lst) 
    ...:  shuffle(temp) 
    ...:  if max(sum(1 for x in g) for k, g in groupby(temp)) <= limit: 
    ...:   return tries #return temp 
    ...:  return pseudo_shuffle(lst, limit, tries=tries+1) 

In [5]: colors = 30*['red', 'blue', 'green', 'yellow'] 

In [6]: sizes = [1] * 20 + [2] * 20 + [3] * 20 + [4] * 20 + [5] * 20 + [6] * 20 

In [7]: Counter([pseudo_shuffle(colors, 4) for _ in range(1000)]) 
Out[7]: Counter({1: 751, 2: 200, 3: 38, 4: 10, 5: 1}) 

In [8]: Counter([pseudo_shuffle(sizes, 4) for _ in range(1000)]) 
Out[8]: Counter({1: 954, 2: 44, 3: 2})