How To Constrain Items With Multiple Randomly Selected Positions So That The Average Position For Each Is Within A Certain Range

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 item

Solution 1:

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.

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 python3import math
import collections
import random

BaseNode = collections.namedtuple('BaseNode', 'sum value ways run prev_node')
classNode(BaseNode):
    defmerge(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)

    defextract_group(self):
        values = []
        node = self
        while node.value isnotNone:
            node.run.remove(node.value)
            values.append(node.value)
            node = node.prev_node
        returnsorted(values)


defrandom_next_group_from_runs (runs):
    runs_by_count = {}
    # organize by countfor 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())
    if6 < len(runs_by_count[largest]):
        largest = largest + 1else:
        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+1notin 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 notin 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 notin 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 notin 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+1notin 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 notin 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 = 903deftry_sum():
        yield avg
        i = 1whileTrue:
            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 inrange(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 = 0while attempt == 0or0 < len(bad_groups):
    attempt = attempt + 1# We add a few groups to bad groups in principle.for i inrange(attempt):
        if20 < len(groups):
            bad_groups.append(groups.pop())
    for group in bad_groups:
        for i in group:
            runs[in_run[i]].add(i)
    bad_groups = []
    whilelen(groups) + len(bad_groups) < 50:
        group = random_next_group_from_runs(runs)
        ifabs(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])

Solution 2:

Take an item, choose a random run and a random position inside that run. 'Put' the item in its place. The next run is non-random: take the 'mirrored' one. I mean if the first run was 0 - (1,36), then next is 7 - (263, 300). If the first is 5 - (187,225), then next is 2 - (74,110). The position in the 'mirrored' run can be random, but since run is pretty wide, I believe you should also divide run into sub-runs and mirror positions also.

import numpy as np
from random import randint

runs = np.array([(1,36), (37,73), (74,110), (111,148), (149,186), (187,225), (226,262), (263, 300)])

#number of runs
numOfRuns =  len(runs)
#number of subruns in a run
numberOfSubruns = 4#maximum error when 'mirroring'
maxMirroringError = 0#number of items
numOfItems = 50#number of positions, must be even
numOfPos = 6#50 items, 6 positions each
items=np.zeros((numOfItems,numOfPos))
for ii inrange(numOfItems):
    #create an array containing "used" runs.
    usedruns=np.zeros(numOfRuns,dtype=bool)
    for jj inrange(0,numOfPos,2):
        whileTrue:
            #choose run index
            run_ind = randint(0,numOfRuns-1)
            #check if it is not usedifnot usedruns[run_ind]:
                break;
        #make run used for this item
        usedruns[run_ind] = True#choose position index
        pos_ind = randint(runs[run_ind][0],runs[run_ind][1])
        #store the result
        items[ii][jj] = pos_ind

        #we need this adjustment in the case of maxMirroringError!=0#or else we get an infinite loop
        adjuster=0whileTrue:
            #find mirrored run
            mirrored_run_ind = numOfRuns - 1 - run_ind+ randint(-(maxMirroringError+adjuster),maxMirroringError+adjuster)
            #apply constraints for mirrored_run_ind to be in [0,numOfRuns)
            mirrored_run_ind = np.min([mirrored_run_ind,numOfRuns-1])
            mirrored_run_ind = np.max([mirrored_run_ind,0])
            adjuster +=1ifnot usedruns[mirrored_run_ind]:
                break;
        #make run used for this item
        usedruns[mirrored_run_ind] = True#get size of a particular subrun
        subrun_size = (runs[run_ind][1]-runs[run_ind][0]) // numberOfSubruns
        #find subrun's index
        subrun_ind = (pos_ind-runs[run_ind][0]) // subrun_size
        #find mirrored subrun's index
        mirrored_subrun_ind = numberOfSubruns - subrun_ind - 1#apply constraints for mirrored_run_ind to be in [0,numberOfSubruns)
        mirrored_subrun_ind = np.min([mirrored_subrun_ind,numberOfSubruns-1])
        mirrored_subrun_ind = np.max([mirrored_subrun_ind,0])
        #find mirrored pos#lower bound
        a = (runs[mirrored_run_ind][1]-runs[mirrored_run_ind][0]) * mirrored_subrun_ind // numberOfSubruns
        #upper bound is lower bound + mirrored subrun size
        b = (runs[mirrored_run_ind][1]-runs[mirrored_run_ind][0]) * (mirrored_subrun_ind + 1) // numberOfSubruns
        #index itself
        mirrored_pos_ind = runs[mirrored_run_ind][0] + randint(a,b)

        #store the result
        items[ii][jj+1] = mirrored_pos_ind
    #check for negativesif (items<0).any():
        print ('negative value encountered!')
        raise;
    #check for same runs
    storedruns=np.zeros(numOfRuns,dtype=bool)
    for pos in items[ii]:
        for kk inrange(numOfRuns):
            if pos>=runs[kk][0] and pos<=runs[kk][1]:
                if storedruns[kk]:
                    print('Same runs for an item encountered!')
                    raise;
                else:
                    storedruns[kk] = kk;
    #print an average of position of an item# print(np.average(items[ii,:]))print('\n')
# print a standard deviation of average of itemsprint(np.std(np.average(items,axis=1)))
# print('\n')# print(items)

You can change numberOfSubruns & maxMirroringError and see what fits your case. Your case (total randomness) is numberOfSubruns=1, maxMirroringError = numOfRuns (equals 8). If you set numberOfSubruns = 4, maxMirroringError = 0, you will get average very close to 148. For your convenience, I put standard deviation calculation of averaged positions to the end.