Произвольная выборка чисел из списка, совокупность которых должна быть как минимум больше данного эталона - PullRequest
Новая
       6

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

0 голосов
/ 30 января 2019

У меня есть список кортежей, состоящих из 1000 идентификаторов объектов и их оценок, то есть:

scored_items = [('14',534.9),('4',86.0),('78',543.21),....].

Пусть T будет агрегированным баллом 20 самых высоких баллов.items.

Это просто.Используя python:

top_20 = sorted(score_items, key=lambda k: k[1],reverse = True)[:20] T = sum(n for _, n in top_20)

Далее, пусть t равняется четверти T.То есть в python: t = math.ceil(T/4)

Мой вопрос : каков наиболее эффективный способ случайного выбора 20 элементов (без замены) из scored_items, чтобы их суммарный балл был равен илибольше чем (но никогда не ниже) t?Они могут включать или не включать элементы из top_20.

Предпочитают ответ в Python и предпочитают не слишком полагаться на внешние библиотеки

Справочная информация: Это алгоритм ранжирования предметов, который доказательство стратегии согласно эзотерической - но полезной - теореме теории игр.Источник: раздел 2.5 в этой статье, или просто прочитайте сноску 18 на странице 11 этой же ссылки.Кстати, стратегия доказательства , по сути, означает, что это трудно для игры.

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

Полагаю, самый простой (и, возможно, наименее эффективный) способ - генерировать случайным образом наборы из 20 предметов, пока сумма их баллов не превысит или не станет равной t.

Но должен быть лучший способ сделать это правильно?

Ответы [ 2 ]

0 голосов
/ 30 января 2019

Вот реализация того, что я упомянул в комментариях.

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

import numpy as np
import math

def normalize(p):
    return p/sum(p)

def get_sample(scored_items, N=20, max_iter = 1000):
    topN = sorted(scored_items, key=lambda k: k[1],reverse = True)[:N]
    T = sum(n for _, n in topN)
    t = math.ceil(T/4)
    i = 0
    scores = np.array([x[1] for x in scored_items])
    p=normalize(scores)
    while i < max_iter:
        sample_indexes = np.random.choice(a=range(len(ids)), size=N, replace=False, p=p)
        sample = [scored_items[x] for x in sample_indexes]
        if sum(n for _, n in sample) >= t:
            print("Found a solution at iteration %d"%i)
            return sample
        i+=1
    print("Could not find a solution after %d iterations"%max_iter)
    return None

Пример того, как его использовать: 

np.random.seed(0)
ids = range(1000)
scores = 10000*np.random.random_sample(size=len(ids))
scored_items = list(zip(map(str, ids), scores))

sample = get_sample(scored_items, 20)
#Found a solution at iteration 0
print(sum(n for _, n in sample))
#139727.1229832652

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

0 голосов
/ 30 января 2019

Хотя я не знаю эффективного способа для огромных списков, что-то подобное работает даже для 1000 или около того элементов.Вы можете сделать немного лучше, если вам не нужно True случайность 

import random 

testList = [x for x in range(1,1000)]
T = sum(range(975, 1000))/4

while True:
    rs = random.sample(testList, 15)
    if sum(rs) >= t: break 

print rs
...