Выделять элементы в соответствии с приблизительным соотношением в Python

См. обновление ниже...

Я пишу симуляцию Python, которая назначает произвольное количество воображаемых игроков одной целью из произвольного пула целей. Цели имеют два разных уровня или доли дефицита, prop_high и prop_low, при приблизительно 3: 1.

Например, если есть 16 игроков и 4 гола, или 8 игроков и 4 гола, два пула целей будут выглядеть следующим образом:

{'A': 6, 'B': 6, 'C': 2, 'D': 2}
{'A': 3, 'B': 3, 'C': 1, 'D': 1}

... с целями A и B, происходящими в 3 раза чаще, чем C и D. 6 + 6 + 2 + 2 = 16, что соответствует числу игроков в симуляции, что хорошо.

Я хочу иметь пул целей, равный количеству игроков и распределяемых таким образом, чтобы было примерно в три раза больше целей prop_high, так как есть цели prop_low.

Какой лучший способ построить алгоритм распределения в соответствии с приблизительным или приблизительным соотношением - что-то, что может обрабатывать округление?

Update:

Предполагая, что 8 игроков, вот как должны распределяться распределения от 2 до 8 целей (звездочки prop_high):

A B C D E F G H
2 6* 2 
3 6* 1 1 
4 3* 3* 1 1 
5 3* 2* 1 1 1 
6 2* 2* 1* 1 1 1 
7 2* 1* 1* 1 1 1 1 
8 1* 1* 1* 1* 1 1 1 1

Эти цифры не соответствуют игрокам. Например, с 5 мячами и 8 игроками, цели A и B имеют большую долю в пуле (3 и 2 соответственно), в то время как цели C, D и E встречаются более редко (1 каждый).

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

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

Я абсолютно уверен, что лучший, более Pythonic способ справиться с подобным алгоритмом, и я уверен, что это относительно общий шаблон дизайна. Я просто не знаю, с чего начать поиск в Google, чтобы найти более элегантный способ обработки такой структуры (вместо метода грубой силы, который я использую сейчас)

import string
import math
letters = string.uppercase
num_players = 8
num_goals = 5
ratio = (3, 1)
prop_high = ratio[0] / float(sum(ratio)) / (float(num_goals)/2)
prop_low = ratio[1] / float(sum(ratio)) / (float(num_goals)/2)
if num_goals % 2 == 1:
 is_odd = True
else:
 is_odd = False
goals_high = []
goals_low = []
high = []
low = []
# Allocate the goals to the pool. Final result will be incorrect.
count = 0
for i in range(num_goals):
 if count < num_goals/2: # High proportion
 high.append(math.ceil(prop_high * num_players))
 goals_high.append(letters[i])
 else: # Low proportion
 low.append(math.ceil(prop_low * num_players))
 goals_low.append(letters[i])
 count += 1
# Make adjustments to the pool allocations to account for rounding and odd numbers
ratio_high_total = len(high)/float(num_players)
overall_ratio = ratio[1]/float(sum(ratio))
marker = (num_players / 2) + 1
offset = num_goals - marker
if num_players == num_goals:
 for i in high:
 high[int(i)] -= 1
elif num_goals == 1:
 low[0] = num_players
elif ratio_high_total == overall_ratio and is_odd:
 high[-1] -= 1
elif ratio_high_total >= overall_ratio: # Upper half of possible goals
 print offset
 for i in range(offset):
 index = -(int(i) + 1)
 high[index] -= 1
goals = goals_high + goals_low
goals_quantities = high + low
print "Players:", num_players
print "Types of goals:", num_goals
print "Total goals in pool:", sum(goals_quantities)
print "High pool:", goals_high, high
print "Low pool:", goals_low, low
print goals, goals_quantities
print "High proportion:", prop_high, " || Low proportion:", prop_low
2 ответа

Вместо того, чтобы пытаться правильно получить дроби, я просто выделил цели по одному в соответствующем соотношении. Здесь генератор allocate_goals задает цель каждому из целей с низким соотношением, затем к каждой из целей с высоким соотношением (повторяется 3 раза). Затем он повторяется. Вызывающий абонент выделяет этот бесконечный генератор с требуемым номером (числом игроков) с помощью itertools.islice.

import collections
import itertools
import string
def allocate_goals(prop_low, prop_high):
 prop_high3 = prop_high * 3
 while True:
 for g in prop_low:
 yield g
 for g in prop_high3:
 yield g
def allocate(goals, players):
 letters = string.ascii_uppercase[:goals]
 high_count = goals // 2
 prop_high, prop_low = letters[:high_count], letters[high_count:]
 g = allocate_goals(prop_low, prop_high)
 return collections.Counter(itertools.islice(g, players))
for goals in xrange(2, 9):
 print goals, sorted(allocate(goals, 8).items())

Он дает ответ:

2 [('A', 6), ('B', 2)]
3 [('A', 4), ('B', 2), ('C', 2)]
4 [('A', 3), ('B', 3), ('C', 1), ('D', 1)]
5 [('A', 3), ('B', 2), ('C', 1), ('D', 1), ('E', 1)]
6 [('A', 2), ('B', 2), ('C', 1), ('D', 1), ('E', 1), ('F', 1)]
7 [('A', 2), ('B', 1), ('C', 1), ('D', 1), ('E', 1), ('F', 1), ('G', 1)]
8 [('A', 1), ('B', 1), ('C', 1), ('D', 1), ('E', 1), ('F', 1), ('G', 1), ('H', 1)]

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

Просто замените allocate_goals следующим:

def allocate_goals(prop_low, prop_high):
 all_goals = prop_low + prop_high * 3
 while True:
 yield random.choice(all_goals)


Некоторое время назад (хорошо, два с половиной года) я спросил вопрос, который, я думаю, будет уместен здесь. Здесь, как я думаю, вы могли бы использовать это: во-первых, создайте список приоритетов, назначенных для каждой цели. В вашем примере, когда первая половина пула целей (округленная вниз) получает приоритет 3, а остальные получают приоритет 1, один из способов сделать это -

priorities = [3] * len(goals) / 2 + [1] * (len(goals) - len(goals) / 2)

Конечно, вы можете создать свой список приоритетов любым способом; он не должен быть половиной 3 с половиной 1 с. Единственное требование состоит в том, чтобы все записи были положительными числами.

Как только у вас есть список, нормализуйте его, чтобы иметь сумму, равную количеству игроков:

# Assuming num_players is already defined to be the number of players
normalized_priorities = [float(p) / sum(priorities) * num_players
 for p in priorities]

Затем примените один из алгоритмов моего вопроса, чтобы округлить эти числа с плавающей запятой до целых чисел, представляющих фактические распределения. Среди полученных ответов есть только два алгоритма, которые правильно выполняют округление и удовлетворяют критерию минимальной дисперсии: скорректированное дробное распределение (включая пункт "Обновление" ) и минимизация ошибки округления. Удобно, что оба они работают для не отсортированных списков. Вот мои реализации Python:

import math, operator
from heapq import nlargest
from itertools import izip
item1 = operator.itemgetter(1)
def floor(f):
 return int(math.floor(f))
def frac(f):
 return math.modf(f)[0]
def adjusted_fractional_distribution(fn_list):
 in_list = [floor(f) for f in fn_list]
 loss_list = [frac(f) for f in fn_list]
 fsum = math.fsum(loss_list)
 add_list = [0] * len(in_list)
 largest = nlargest(int(round(fsum)), enumerate(loss_list),
 key=lambda e: (e[1], e[0]))
 for i, loss in largest:
 add_list[i] = 1
 return [i + a for i,a in izip(in_list, add_list)]
def minimal_roundoff_error(fn_list):
 N = int(math.fsum(fn_list))
 temp_list = [[floor(f), frac(f), i] for i, f in enumerate(fn_list)]
 temp_list.sort(key = item1)
 lower_sum = sum(floor(f) for f in fn_list)
 difference = N - lower_sum
 for i in xrange(len(temp_list) - difference, len(temp_list)):
 temp_list[i][0] += 1
 temp_list.sort(key = item2)
 return [t[0] for t in temp_list]

Во всех моих тестах оба этих метода в точности эквивалентны, поэтому вы можете выбрать один из них для использования.

Вот пример использования:

>>> goals = 'ABCDE'
>>> num_players = 17
>>> priorities = [3,3,1,1,1]
>>> normalized_priorities = [float(p) / sum(priorities) * num_players
 for p in priorities]
[5.666666..., 5.666666..., 1.888888..., 1.888888..., 1.888888...]
>>> minimal_roundoff_error(normalized_priorities)
[5, 6, 2, 2, 2]

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

>>> def rlist(l):
... return list(reversed(l))
>>> rlist(minimal_roundoff_error(rlist(normalized_priorities)))
[6, 5, 2, 2, 2]

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

def remainder_distribution(fn_list):
 N = math.fsum(fn_list)
 rn_list = [int(round(f)) for f in fn_list]
 remainder = N - sum(rn_list)
 first = 0
 last = len(fn_list) - 1
 while remainder > 0 and last >= 0:
 if abs(rn_list[last] + 1 - fn_list[last]) < 1:
 rn_list[last] += 1
 remainder -= 1
 last -= 1
 while remainder < 0 and first < len(rn_list):
 if abs(rn_list[first] - 1 - fn_list[first]) < 1:
 rn_list[first] -= 1
 remainder += 1
 first += 1
 return rn_list

licensed under cc by-sa 3.0 with attribution.