Phân loại thuật toán để giữ các giá trị bằng nhau tách biệt

Question

Các thử nghiệm tâm lý thường yêu cầu bạn giả ngẫu nhiên lệnh thử nghiệm, để các thử nghiệm dường như ngẫu nhiên, nhưng bạn không nhận được quá nhiều thử nghiệm tương tự liên tiếp (điều này có thể xảy ra hoàn toàn ngẫu nhiên) đặt hàng).

Hãy nói rằng màn hình hiển thị hình ảnh của mỗi phép thử có một màu sắc và kích thước:

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) 

Và chúng ta có thể nhìn vào số lượng tối đa của các thử nghiệm liên tiếp có cùng giá trị cho một trong hai tài sản sử dụng chức năng này:

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 

Output:

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

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

có bất kỳ thuật toán bạn biết điều đó sẽ cho phép giảm thiểu các lần chạy liên tiếp của một trong hai hoặc cả hai thuộc tính, hoặc ít nhất giữ cho các giá trị này chạy dưới một độ dài được chỉ định? Nếu sau này, giả sử không quá 4 trong một hàng cùng màu hoặc kích thước.

---

Những gì tôi đã cố gắng:

Các giải pháp tôi có bây giờ về cơ bản không một chút thông minh bogosort, trong đó có được hiệu quả khủng khiếp. Về cơ bản:

• Quý khách nghỉ ngơi toàn bộ danh sách thành những phần có chứa tất cả các hoán vị của các thuộc tính: nếu bạn phá vỡ display_list vào khối có độ dài 24, mỗi đoạn có mỗi màu sắc kết hợp với mỗi kích thước. Giả sử rằng danh sách thử nghiệm luôn luôn có thể được chia thành các khối hoán vị này, vì bạn biết những hoán vị nào là từ thiết kế của thử nghiệm.
• Bạn chọn độ dài tối đa cho mỗi đoạn
• Bạn trộn từng đoạn cho đến khi độ dài chạy cho mỗi đoạn thấp hơn giá trị tối đa (điều này thực sự có nghĩa là trong danh sách dùng thử tổng thể, thời gian chạy của bạn có thể dài gấp đôi, vì bạn có thể có thời gian chạy ở cuối đoạn này và bắt đầu đoạn tiếp theo)

Answer 1

Câu hỏi: Có bất kỳ thuật toán bạn biết điều đó sẽ cho phép giảm thiểu chạy liên tiếp của một trong hai hoặc cả hai tài sản, hoặc ít nhất là giữ cho những chạy dưới một chiều dài quy định?

Có. Có một thuật toán dễ dàng để làm điều này bằng cách đơn giản giảm xác suất của một màu hoặc kích thước được chọn nếu nó đã xảy ra trong một lần chạy.

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 

Lưu ý, phương pháp này đòi hỏi ít nỗ lực hơn các câu trả lời khác sử dụng kỹ thuật chọn lại để tránh chạy. Ngoài ra, lưu ý các lần chạy bị mờ dần dần thay vì tất cả cùng một lúc như trong các câu trả lời khác.

Answer 2

Xin lỗi, đây không phải là câu trả lời, nhưng khó đăng mã trong nhận xét. Đây là một cách đơn giản hơn để viết consecutive_properties chức năng

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

Khi tôi hiểu câu hỏi của bạn đúng, tôi sẽ cố gắng để tắt chức năng này thành một câu trả lời :)

Answer 3

Bạn đang rõ ràng không quan tâm đến bất cứ điều gì như ngẫu nhiên đúng , vì vậy nếu bạn xác định số liệu khoảng cách và vẽ chuỗi của bạn một cách ngẫu nhiên, bạn có thể từ chối bất kỳ bản vẽ mới nào nếu khoảng cách đó "quá gần" đối với bản vẽ trước đó và chỉ cần vẽ lại.

Nếu bạn vẽ từ một tập hợp hữu hạn (ví dụ, một gói thẻ) thì toàn bộ có thể là là cọc vẽ, và sắp xếp của bạn sẽ bao gồm hoán đổi hai phần tử khi một cặp gần được tìm thấy, nhưng cũng từ chối một đối tác hoán đổi nếu phần tử hoán đổi sẽ trở thành không thể chấp nhận được, do đó, mỗi bước hoán đổi để lại toàn bộ thiết lập được cải thiện.

Nếu tiêu chí của bạn không quá khó để thỏa mãn, điều này sẽ chấm dứt rất nhanh.

Answer 4

Như ddyer cho biết, bạn quan tâm đến tính ngẫu nhiên thay vì sắp xếp.Giải pháp của tôi ở đây sẽ là:

1. Chọn ngẫu nhiên một phần tử từ danh sách nguồn của bạn
2. Chọn một vị trí ngẫu nhiên tôi ra khỏi danh sách điểm đến của bạn
3. Insert A tại vị trí tôi tới đích. list
4. Kiểm tra xem danh sách đích có hợp lệ hay không. Nếu không, khôi phục lại trạng thái trước đó và lặp lại

Một đoạn làm việc:

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 

Lưu ý rằng bạn không cần phải kiểm tra tất cả các mục trong danh sách điểm đến mỗi lần, K ở bên trái và bên phải xung quanh mục chèn mới (không được thực hiện trong đoạn mã)

Sửa:

• Bạn có thể sử dụng groupby trong has_consecutive_keys (nhưng không có sắp xếp!)

Answer 5

Nếu khả năng của các yếu tố liên tiếp không phải là rất cao (như trong ví dụ của bạn), tôi chỉ đơn giản là sẽ cải tổ nếu tình trạng này không được đáp ứng. Như bạn có thể thấy, hầu hết thời gian bạn có thể dùng thử, vì vậy nó khá hiệu quả.

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