Алгоритм сортировки для разделения равных значений

Ответ 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

Обратите внимание: этот подход требует меньших усилий, чем другие ответы, которые используют методы повторного выбора, чтобы избежать прогонов. Кроме того, обратите внимание, что пробеги постепенно исчезают, а не все одновременно, как и в других ответах.

Ответ 2

Вы явно не заботитесь о чем-то вроде истинной случайности, поэтому, если вы определяете метрику расстояния и произвольно производите свою последовательность, вы можете отклонить любую новую ничью, если расстояние "слишком близко" к предыдущей ничьей, и просто снова нарисуй.

Если вы рисуете из конечного набора (скажем, пакета карт), то весь набор может быть ничьей, и ваш вид будет состоять из замены двух элементов при закрытии пара, но также отклонить партнера по обмену, если элемент с заменой станет неприемлемым, поэтому каждый шаг свопа оставляет весь набор улучшенным.

Если ваши критерии не так сложно удовлетворить, это очень быстро закончится.

Ответ 3

Как сказал ddyer, вас интересует случайность, а не сортировка. Мое решение здесь:

• Выберите случайный элемент из вашего исходного списка
• Выберите случайную позицию я из вашего списка адресатов
• Вставьте A в положение я в dest. список
• Проверьте, действителен ли список адресатов. Если нет, восстановите предыдущее состояние и повторите

Рабочий фрагмент:

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

Обратите внимание, что вам не нужно каждый раз проверять все элементы в списке адресатов, K слева и справа вокруг вставленного нового элемента (не реализовано в фрагменте)

Edit

• Вы можете использовать groupby в has_consecutive_keys (но без сортировки!)

Ответ 4

Если вероятность последовательных элементов не очень высока (как в вашем примере), я бы просто перетасовал, если условие не выполнено. Как вы можете видеть, большую часть времени вы уходите с одной попытки, поэтому она достаточно эффективна.

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

Ответ 5

Извините, это не ответ, но мне сложно опубликовать код в комментариях. Вот более простой способ написать функцию 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)))

Когда я правильно понимаю ваш вопрос, я попытаюсь превратить это в ответ:)