Создайте множество ограниченных случайных перестановок списка.
https://stackoverflow.com/questions/93353
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужно составить случайный список перестановок.Элементами может быть что угодно, но не предполагается, что это целые числа от 0 до x-1.Я хочу составить списки y, каждый из которых содержит элементы z.Правила заключаются в том, что ни один список не может содержать один и тот же элемент дважды и что во всех списках количество раз, когда каждый элемент используется, одинаково (или как можно ближе).Например, если мои элементы — 0,1,2,3, y — 6, а z — 2, то одно из возможных решений:
0,3 1,2 3,0 2,1 0,1 2,3
Каждая строка содержит только уникальные элементы, и ни один элемент не использовался более 3 раз.Если бы y было 7, то 2 элемента использовались бы 4 раза, остальные 3.
Решение
Это можно улучшить, но, похоже, оно справляется со своей задачей (Python):
import math, random
def get_pool(items, y, z):
slots = y*z
use_each_times = slots/len(items)
exceptions = slots - use_each_times*len(items)
if (use_each_times > y or
exceptions > 0 and use_each_times+1 > y):
raise Exception("Impossible.")
pool = {}
for n in items:
pool[n] = use_each_times
for n in random.sample(items, exceptions):
pool[n] += 1
return pool
def rebalance(ret, pool, z):
max_item = None
max_times = None
for item, times in pool.items():
if times > max_times:
max_item = item
max_times = times
next, times = max_item, max_times
candidates = []
for i in range(len(ret)):
item = ret[i]
if next not in item:
candidates.append( (item, i) )
swap, swap_index = random.choice(candidates)
swapi = []
for i in range(len(swap)):
if swap[i] not in pool:
swapi.append( (swap[i], i) )
which, i = random.choice(swapi)
pool[next] -= 1
pool[swap[i]] = 1
swap[i] = next
ret[swap_index] = swap
def plist(items, y, z):
pool = get_pool(items, y, z)
ret = []
while len(pool.keys()) > 0:
while len(pool.keys()) < z:
rebalance(ret, pool, z)
selections = random.sample(pool.keys(), z)
for i in selections:
pool[i] -= 1
if pool[i] == 0:
del pool[i]
ret.append( selections )
return ret
print plist([0,1,2,3], 6, 2)
Другие советы
Хорошо, один из способов приблизить это:
1 - перетасуйте свой список
2 — возьмите первые элементы y, чтобы сформировать следующую строку
4 — повторять (2), пока в списке есть номера
5 – если вам не хватает номеров, чтобы закончить список, перетасуйте исходный список и возьмите недостающие элементы, следя за тем, чтобы не пересдавать номера.
6. Начните заново с шага (2), пока вам нужны строки.
Я думаю, что это должно быть настолько случайно, насколько это возможно, и наверняка будет соответствовать вашим критериям.Плюс у вас очень мало тестов на дублирующиеся элементы.
Во-первых, вы всегда можете отсортировать список случайным образом, так что давайте не будем беспокоиться о «случайных перестановках» (сложно);и просто беспокойтесь о том, чтобы 1) сделать перестановки (легко) и 2) рандомизировать их (легко).
Если вам нужны «по-настоящему» случайные группы, вы должны признать, что рандомизация по своей природе не допускает ограничения «равномерного распределения» результатов — вы можете получить это или получить серию похожих результатов.Если вы действительно хотите равномерного распределения, сначала сделайте наборы равномерно распределенными, а затем рандомизируйте их как группу.
Нужно ли вам использовать каждый элемент множества x равномерно?Из правил не ясно, что я не мог просто сделать следующую интерпретацию:
Обратите внимание на следующее:«Во всех списках количество раз использования каждого элемента одинаково (или максимально близко)»
Основываясь на этом критерии и правиле z < x*, я постулирую, что вы можете просто перечислить все элементы во всех списках.Таким образом, вы автоматически составляете список y из элементов, пронумерованных до позиции z.Ваш пример не соответствует приведенному выше правилу так точно, как моя версия.Используя ваш пример x={0,1,2,3} y=6 и z=2, я получаю:0,1 0,1 0,1 0,1 0,1 0,1
Я не использовал 2 или 3, но вы не говорили, что я должен использовать их все.Если бы мне пришлось использовать их все и мне не хотелось бы доказывать, что я «настолько близок» к равномерному использованию, я бы просто перечислил все элементы в списках, вот так:0,1 2,3 0,1 2,3 0,1 2,3
Наконец, предположим, что мне действительно нужно использовать все элементы.Чтобы подсчитать, сколько раз может повторяться каждый элемент, я просто беру (y*z)/(количество x).Таким образом, мне не придется сидеть и беспокоиться о том, как разделить элементы в списке.Если есть остаток или результат меньше 1, то я знаю, что не получу точного количества повторений, поэтому в таких случаях не имеет большого значения пытаться тратить вычислительную энергию, чтобы сделать его идеальным.Я утверждаю, что самый быстрый результат — это просто перечислить, как указано выше, и использовать приведенные здесь расчеты, чтобы показать, почему был достигнут или не был достигнут идеальный результат.Можно было бы реализовать причудливый алгоритм, позволяющий определить из этого расчета, сколько позиций будет повторяться, но «он слишком длинный, чтобы поместиться здесь, на полях».
*Каждый список содержит одинаковое количество элементов z, поэтому будет невозможно создавать списки, в которых z больше x, и при этом соблюдать правило, согласно которому ни один список не может содержать один и тот же элемент дважды.Следовательно, это правило требует, чтобы z не могло быть больше x.
Судя по новым деталям в комментариях, решением может быть просто реализация стандартного алгоритма генерации случайных перестановок.Здесь подробно обсуждаются алгоритмы генерации случайных перестановок:
http://www.techuser.net/randpermgen.html
(Из поиска Google:генерация случайной перестановки)
Это работает в Ruby:
# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
list.uniq! # Never trust the user. We want no repetitions.
equalizer = {}
list.each { |element| equalizer[element] = 0 }
results = []
# Do this until we get as many results as desired
while results.size < y
pool = []
puts pool
least_used = equalizer.each_value.min
# Find how used the least used element was
while pool.size < z
# Do this until we have enough elements in this resultset
element = nil
while element.nil?
# If we run out of "least used elements", then we need to increment
# our definition of "least used" by 1 and keep going.
element = list.shuffle.find do |x|
!pool.include?(x) && equalizer[x] == least_used
end
least_used += 1 if element.nil?
end
equalizer[element] += 1
# This element has now been used one more time.
pool << element
end
results << pool
end
return results
end
Пример использования:
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here
