python - 如何约束具有多个随机选择位置的项目，使每个项目的平均位置在一定范围内

Question

问题:总共，我有 1-300 个职位需要填写，我有 50 个项目，每个项目有 6 个独特的职位可供选择(总共 300 个职位)。每个项目的平均排名需要在 145-155 范围内(越接近 150 越好)

约束:对于每个项目，其 6 个位置中的每一个都必须落在固定范围列表(称为运行)内，但不能在同一运行内，

例如运行次数为:[(1,36), (37,73), (74,110), (111,148), (149,186), (187,225), (226,262), (263, 300)] 。因此，第 1 项的位置可以为 1、38、158、198、238、271 - 因此不能在同一次运行中出现两次。

选择的位置应该是随机的 - 或尽可能随机

我遇到的问题:将随机选择的位置限制为平均值 150(或非常接近)似乎非常困难。我已经尝试了代码的各种不同实现，但大多数都会导致它卡在接近末尾的位置(由于没有足够的位置可供选择)，或者不会非常接近。我最好的尝试只是涉及我放置的 if 语句，至少尝试限制范围，但它仍然只能得到大约 130-170 的范围。这感觉像是一个非常糟糕的方法，我想知道是否有一种方法可以通过算法来完成它，而不是仅仅粘贴 if 语句以希望某些东西能起作用。

我对随机创可贴限制的最佳尝试:https://pyfiddle.io/fiddle/dfc6dfd1-1e12-46df-957c-d7ae0e94fbe3/?i=true

^ 正如您所看到的，平均值有所不同，大多数情况都在可接受的范围内，有些只是偏离/非常偏离

我花了几个星期的时间来解决这个问题，但真的想不出什么办法可以将其限制在适当的平均值(145-155)，并希望在这里得到任何帮助

Answer 1

这种方法使用动态规划来随机提取尽可能好的组 50 次。然后，它将不完美的东西与一些好的东西一起放回原处，并尝试同样的事情。它不断这样做，同时放宽完美的定义，直到获得 50 个可接受的组。

速度很慢。 (在我的笔记本电脑上大约 20 秒。)但它经常使所有组的平均值完全相同。在多次运行中，我没有看到任何组超出范围[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])