如何限制具有多个随机选择位置的项目，以使每个项目的平均位置在一定范围内 [英] How to constrain items with multiple randomly selected positions so that the average position for each is within a certain range
问题描述
问题:我总共需要填写1-300个职位，我有50个职位，每个项目都有6个唯一职位可供选择(总共300个职位).这些项目中每一项的平均排名都必须在145-155之间(越接近150越好)
Problem: In total, I have 1-300 positions to fill in, I have 50 items, each item has 6 unique positions to choose (300 total positions). The average position for each of these items needs to be in range 145-155 (the closer to 150 the better)
约束:对于每个项目，其6个位置中的每个位置都必须位于固定范围(称为运行)列表中，但不能位于同一运行中，
Constraints: For each item, each of its 6 positions must fall within a list of fixed ranges (called runs), but not be within the same run,
例如运行是: [(1,36)，(37,73)，(74,110)，(111,148)，(149,186)，(187,225)，(226,262)，(263、300)] .因此项目1的位置可以为1、38、158、198、238、271-因此不在同一运行中两次.
e.g. The runs are: [(1,36), (37,73), (74,110), (111,148), (149,186), (187,225), (226,262), (263, 300)]. So item 1 can have position 1, 38, 158, 198, 238, 271 - so not within the same run twice.
所选位置应该是随机的-或尽可能随机
The positions chosen should be random - or as random as possible
我遇到的问题:将随机选择的位置限制为平均150个(或非常接近)似乎很困难.我已经尝试过各种不同的代码实现，但是大多数都会导致代码接近尾声(由于没有足够的位置可供选择)或距离不太近.我最好的尝试只是涉及我是否放置了至少要限制范围的语句，但是它仍然只能达到130-170左右的范围.这似乎是一种非常糟糕的方法，我想知道是否有一种算法可以做到这一点，而不是仅仅糊涂一下语句是否希望某些东西能起作用.
The issue I'm having: Constraining the randomly selected positions to be an average of 150 (or very close) seems to be really difficult. I've tried various different implementations of the code but most will result in it hanging close to the end (due to not having enough positions to choose from), or don't get very close. My best attempt just involves if statements I've placed to at least try to restrict the range but it still only gets a range of around 130-170. This feels like a really poor method and I was wondering if there was a way to do it algorithmically instead of just pasta'ing if statements in hopes something will work.
我对随机创可贴限制的最佳尝试:https://pyfiddle.io/fiddle/dfc6dfd1-1e12-46df-957c-d7ae0e94fbe3/?i=true
My best attempt with random band-aid restrictions: https://pyfiddle.io/fiddle/dfc6dfd1-1e12-46df-957c-d7ae0e94fbe3/?i=true
^如您所见，平均值有所不同，大多数情况都在可接受的范围内，而有些则处于关闭/真正关闭状态
^ as you can see the averages vary, with most things being in an acceptable range and some just being off/really off
我已经花了几周的时间，但实际上无法考虑将其限制在适当的平均水平(145-155)，并希望在此寻求任何帮助
I've spent several weeks on this but genuinely cannot think of anything to restrict it to an appropriate average (145-155) and was hoping for any help here
推荐答案
此方法使用动态编程来随机抽取尽可能好的50个组.然后，它会将不完美的对象与一些好的对象一起返回，并尝试相同的操作.它会继续这样做，同时放宽对Perfect的定义，直到获得50个可接受的组为止.
This approach uses dynamic programming to randomly extract as good a group as it can 50 times. It then throws the imperfect ones back in with a few good ones and tries the same thing. It keeps doing this while relaxing the definition of perfect until it gets 50 acceptable groups.
很慢.(在我的笔记本电脑上大约需要20秒.)但是，它经常会使所有组的平均值完全相同.在许多次运行中，我没有看到单个组超出 [150.0，151.0] 的范围.
It is slow. (About 20 seconds on my laptop.) But it frequently gets all groups to have the exact same average. Across a number of runs I did not see a single group out of the range [150.0, 151.0].
#! /usr/bin/env python3
import math
import collections
import random
BaseNode = collections.namedtuple('BaseNode', 'sum value ways run prev_node')
class Node(BaseNode):
def merge(self, other):
if self.sum != other.sum:
print(self)
print(other)
raise Exception('Can only merge nodes with the same sum.')
ways = self.ways + other.ways
if self.ways <= random.randint(1, ways):
return Node(sum=self.sum, value=self.value, ways=ways,
run=self.run, prev_node=self.prev_node)
else:
return Node(sum=other.sum, value=other.value, ways=ways,
run=other.run, prev_node=other.prev_node)
def extract_group(self):
values = []
node = self
while node.value is not None:
node.run.remove(node.value)
values.append(node.value)
node = node.prev_node
return sorted(values)
def random_next_group_from_runs (runs):
runs_by_count = {}
# organize by count
for run in runs:
count = len(run)
if count in runs_by_count:
runs_by_count[count].append(run)
else:
runs_by_count[count] = [run]
required_runs = []
optional_runs = []
largest = max(runs_by_count.keys())
if 6 < len(runs_by_count[largest]):
largest = largest + 1
else:
required_runs = runs_by_count[largest]
for count, these_runs in runs_by_count.items():
if count < largest:
optional_runs.extend(these_runs)
# We start with the empty sum.
node_by_sum_by_count = {0: {0: Node(sum=0, value=None, ways=1, run=None, prev_node=None)}}
# We update to use a value from each required run.
for run in required_runs:
new_node_by_sum_by_count = {}
for count, node_by_sum in node_by_sum_by_count.items():
if count+1 not in new_node_by_sum_by_count:
new_node_by_sum_by_count[count+1] = {}
new_node_by_sum = new_node_by_sum_by_count[count+1]
for s, node in node_by_sum.items():
for i in run:
new_node = Node(sum=s+i, value=i, ways=node.ways, run=run, prev_node=node)
if s+i not in new_node_by_sum:
new_node_by_sum[s+i] = new_node
else:
# This merge hides the random choice of which one to take.
new_node_by_sum[s+i] = new_node_by_sum[s+i].merge(new_node)
node_by_sum_by_count = new_node_by_sum_by_count
# We may use a value from each optional run.
for run in optional_runs:
new_node_by_sum_by_count = {}
for count, node_by_sum in node_by_sum_by_count.items():
# The options where we do not use this run.
if count not in new_node_by_sum_by_count:
new_node_by_sum_by_count[count] = {}
new_node_by_sum = new_node_by_sum_by_count[count]
for s, node in node_by_sum.items():
if s not in new_node_by_sum:
new_node_by_sum[s] = node
else:
new_node_by_sum[s] = new_node_by_sum[s].merge(node)
# The options where we do use this run.
if count+1 not in new_node_by_sum_by_count:
new_node_by_sum_by_count[count+1] = {}
new_node_by_sum = new_node_by_sum_by_count[count+1]
for s, node in node_by_sum.items():
for i in run:
new_node = Node(sum=s+i, value=i, ways=node.ways, run=run, prev_node=node)
if s+i not in new_node_by_sum:
new_node_by_sum[s+i] = new_node
else:
# This merge hides the random choice of which one to take.
new_node_by_sum[s+i] = new_node_by_sum[s+i].merge(new_node)
node_by_sum_by_count = new_node_by_sum_by_count
# Widening sums close to 903
avg = 903
def try_sum():
yield avg
i = 1
while True:
yield avg - i
yield avg + i
i = i+1
# We only want groups with 6 elements.
node_by_sum = node_by_sum_by_count[6]
for i in try_sum():
if i in node_by_sum:
return node_by_sum[i].extract_group()
runs = [
set(range(1, 37)),
set(range(37, 74)),
set(range(74, 111)),
set(range(111, 149)),
set(range(149, 187)),
set(range(187, 226)),
set(range(226, 263)),
set(range(263, 301)),
]
in_run = {}
for i in range(len(runs)):
for j in runs[i]:
in_run[j] = i
#runs = [ set(range(i*36+1, i*36+37)) for i in range(8) ]
groups = []
bad_groups = []
attempt = 0
while attempt == 0 or 0 < len(bad_groups):
attempt = attempt + 1
# We add a few groups to bad groups in principle.
for i in range(attempt):
if 20 < len(groups):
bad_groups.append(groups.pop())
for group in bad_groups:
for i in group:
runs[in_run[i]].add(i)
bad_groups = []
while len(groups) + len(bad_groups) < 50:
group = random_next_group_from_runs(runs)
if abs(sum(group) - 903) <= math.floor(attempt/5.0):
groups.append(group)
else:
bad_groups.append(group)
random.shuffle(groups)
for group in groups:
print([sum(group), group])
这篇关于如何限制具有多个随机选择位置的项目，以使每个项目的平均位置在一定范围内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
