Как стать автором
Обновить

Комментарии 77

К счастью, если вы готовы примириться с несколькими небольшими неточностями, то из людей можно сделать довольно хороший ГСЧ, не спрашивая более двух раз.

А как вы построите распределение, которое вы выравниваете? Если вы примиряетесь с неточностями, то можете просто использовать простой ГПСЧ, который можно считать в столбик на бумажке/в уме.
Может быть взять число пи и брать постепенно цифру за цифрой? А если распределение будет неравномерным — начать выравнивать его при помощи ЛП.
Инициализировать чем будете? У человека случайное число от 0 до MAX_LONG спросите? Так при таком вопросе распределение очень плохим окажется. И его нормализовать заметно сложнее будет.
Все зависит от задачи. Для чего это применяется?
Для криптографии, например, не подойдет. Для каких то других применений будет достаточно закольцованного списка из 10 чисел. Где то линейный конгруентный метод. И Т. Д.

Самое простое — попросить кого-нибудь: «Эй, выбери случайное число от одного до десяти!». Человек отвечает: «Семь!». Отлично! Теперь у вас есть число. Однако вы начинаете задаваться вопросом, является ли оно равномерно распределённым?

ИМХО, если Вам нужно всего одно число, то не нужно задаваться вопросом «является ли оно равномерно распределенным». У Вас нет репрезентативности, чтобы опровергнуть/доказать что либо.
Поэтому такое число вам подходит. Потому что просто соответствует заданному критерию.
Эй, смотрите, я даже кусок вашего кода нашел.
image

А с чего вы взяли, что один и тот же человек каждый раз будет на вопрос "выбери случайное число от 1 до 10" отвечать 7? Пока у вас есть один ответ — вы не можете этого знать.

Ну нет. У нас же есть не просто число, у нас есть алгоритм его получения! Так что вопрос про равномерную распределённость корректен.

семь, Пушкин, нос — имеют репрезентативность в русскоязычной среде.

Взять массив из 10 чисел и прогнать его перестановками n раз, где n случайное целое число в нужном нам диапазоне?

Понятно, что любая надстройка (усложняющая функция) над плохим человеческим ГСЧ в результате на очень большой выборке позволит статистически предугадать следующее число с большой вероятностью. Это нерешаемая проблема, т.к. для истинно случайной последовательности нужен просто хороший ГСЧ.

Интересен другой момент. Допустим, что у нас нет комнаты с людьми, а только мы сами. Нет ни игральной кости, ни чего-либо ещё, только наш организм. Есть ли какой-нибудь способ сгенерировать случайную последовательность, пусть даже очень медленно? Человеческий организм достаточно сложный, в нём много случайных процессов различной природы, соответственно и различных источников энтропии, но можно ли их как-нибудь считать нашими органами чувств и воспроизвести в виде последовательности? Чисто теоретически подобный навык был бы полезен с точки зрения информационной безопасности.

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

Можно, хотя это нарушает предложенные условия. Часы — внешний источник. Допустим, что у человека нет внешних ориентиров.

Приведу пример. Многие, наверное, знакомы со звоном в ушах в очень тихой обстановке. Иногда я у себя замечаю, что в одном ухе тон этого звона дискретно изменяется, т.е. я ощущаю два отчетливых переключающихся тона. Если использовать стук сердца как тактовый генератор, то можно в моменты удара сердца регистрировать тон в ухе. Я так и не проделал этот эксперимент, хотя очень хотелось бы оценить случайность полученной последовательности. Это довольно сложно и не практично, но тем не менее. Возможно есть другие способы?
Убрать часы можно считая удары сердца за, как человеку кажется, пять минут.
У всех этих способов есть один нюанс, мы должны заранее знать распределение которое получается и надеяться что это распределение не изменяется со временем.
Есть способ не рассчитывать на человеческое поведение и рассмотреть другой способ генерации не равномерного распределения.
Например спросить имя-фамилию и случайное число, контатенировать и посчить хэш.
Так как хэш мы выбираем сами — мы можем узнать его распределение и уже по этим значениям применить продолжение статьи. По моему мнению такой подход будет более логичен.

По распределениям хэш-функций много статей не нашел, может плохо искал. Просто для ознакомления и объяснения почему обычно используемые хэш-функции не дают равномерного распределения: research.neustar.biz/2012/02/02/choosing-a-good-hash-function-part-3
Вариантов куча, главное их придумать и доработать:
1. Последовательно плевать в одном направлении, сортировать расстояние до плевков.
2. Ронять любой предмет (если есть) на палец и отмечать «успел отдёрнуть или нет».
3. Считать количество ударов сердца за время, на которое можете задержать дыхание «и брать простую функцию от этого числа» (с).
4. Сидеть и ждать, какая нога раньше зачешется — левая или правая (рандом 0 или 1).
Достаточно или ещё нагенерировать?
Вы немного не уловили суть. Прежде всего имелись ввиду способы генерации последовательности из головы без каких-либо внешних вспомогательных средств. Из выше предложенного более-менее подходит последний пункт. А сможете не задумываясь длительное время произносить числа, кажущиеся вам случайными? Если последовательность будет достаточно длинной, то предполагаю, что можно будет статистически с высокой вероятностью предугадать следующее сказанное вами число. И это проблема.
Можно с высокой долей вероятности предположить, что любая последовательность «из головы» или слишком предсказуема или встречающиеся в ней элементы не будут равномерно распределены.
Поэтому, в Вашем примере, нужен сторонний источник «вдохновения» (например сделать N оборотов с закрытыми глазами и посмотреть, куда направлен взгляд).
Когда мне было нужно так делать, быстро придумывал и запоминал достаточно большое число (двадцать три миллиона шестьсот восемьдесят шесть тысяч триста восемь — 23686308) и считал числовой корень (9). Вполне себе от 0 до 9 получается. Чем больше число, тем честней будет распределение.
Вполне себе от 0 до 9 получается

Всё-таки от 1 до 9, вероятно?

Да, вы абсолютно правы.

А ещё можно делать одну итерацию сложения цифр и находить остаток от деления на подходящий делитель.

можно 6 раз подбросить монетку, полученное двоичное число разделить на 7, прибавить 1 и округлить к ближайшему целому

без доступа к монетам
Записываем все ответы на бумажку, затем обрабатываем скользящим окном с шириной и шагом 2:

n = n+1: значение отбрасывается
n > n+1: возвращается 1
n < n+1: возвращается 0


Код
import matplotlib.pyplot as plt
from random import choices
from itertools import islice
from collections import Counter

def human_random(count):
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    weights = [3.4, 8.5, 10.0, 9.7, 12.2, 9.8, 28.1, 10.9, 5.4, 1.9]
    return choices(numbers, weights, k=count)  

def chunks(seq, size):
    it = iter(seq)
    while True:
       chunk = list(islice(it, size))
       if not chunk or len(chunk) < size:
           return
       yield chunk

def extract_random(seq):
    bit = lambda x, y: None if x == y else int(x > y)
    for n1, n2 in chunks(seq, 2):
        x = bit(n1, n2)
        if x is None:
            continue
        yield x

def pack_bits(bits):
    return sum([b << i for i, b in enumerate(reversed(bits))])

seq1 = human_random(8500)
bits = extract_random(seq1)

seq2 = (pack_bits(x) for x in chunks(bits, 4))
seq2 = filter(lambda x: 1 <= x <= 10, seq2)

human = Counter(seq1)
extracted = Counter(seq2)

plt.bar(human.keys(), human.values())
plt.bar(extracted.keys(), extracted.values())
plt.show()


Получим битовую последовательность с равномерным распределением 1 и 0, которую уже можно как-нибудь упаковать в 1..10 (правда, чисел на выходе будет сильно меньше). У нас получился самый примитивный "экстрактор случайности фон Неймана".
image
А переставить порядок в ряде чисел от 1 до N никак?
Вы продолжаете их спрашивать и считать их ответы, округляя дробные числа и игнорируя тех, кто думает, что диапазон от 1 до 10 включает 0.
А также игнорируете тех кто сказал уже названные числа.
что тогда ответит 11й человек, если вариантов всего 10 и все они уже названы?
Видимо игнорировать повторы до момента пока все числа не перечислены, после этого начинается новый цикл генерации. Так же как и новая перестановка порядка чисел.

Можно попросить двух людей поиграть в какую-нибудь игру, где шансы близки к 50%. Например, в камень-ножницы-бумагу. Получим источник случайных битов, по одному каждый на розыгрыш. Чтобы была заинтересованность играть хорошо, пусть играют на щелбаны.

Если один из них играет лучше, то будет скос

Для игры камень ножницы бумага, 2-ум играющим завязать глаза и заткнуть уши, проигравшего исследователь пинает под ж.пу, сильно и больно.
итого хватит 3-х чел. без всяких 8 500 и математических преобразований которые без компьютера и не выполнишь, хотя по условию его изначально не должно быть.
проигравшего исследователь пинает под ж.пу, сильно и больно.

У меня так один товарищ игру в мафию проводил, всем раздал бумажки, что они честные жители, а сам имитировал действия мафии и наслаждался.
4 человека играют 2 раза(2 независимые пары, каждая играет 1 раз). Берем XOR от того выиграл ли более высокий игрок или нет(из каждой пары). Таким образом генерируем 6 бит(повторяем 6 раз). Инвертируем каждый 2й бит. Сдвигаем окно из 4х бит на 1 бит вправо если 6й бит==1. Если получаем число вне допустимого range, то переигрываем. Profit.
Ps знаю, это число все ещё не случайно, но bias по максимуму устранен.
А по нормальному можно сделать генератор псевдослучайных чисел на основе буфера бинарных чисел. Изначально в нем одни 0и. Берем xnor 9го и 11го числа(выберите сами любые 2 числа). Записываем результат в самый левый бит. Дальше сдвигаем вправо и повторяем n раз пока не выйдет в рабочий режим. Работает на листочке.

Недостаток вашего метода в том, что нужно знать веса случайного распределения. А как насчет примитивной реализации, которая не требует такого знания?


from random import random

def sample1():
    s = random() ** 2
    return int(s * 10)

def sampleN(n=10):
    return sum(sample1() for _ in range(n)) % 10

Результат, мне кажется, более чем удовлетворительный:


>>> from collections import Counter
>>> Counter(sample1() for _ in range(10000))
Counter({0: 3250,
         1: 1258,
         2: 989,
         3: 832,
         4: 753,
         5: 676,
         6: 656,
         7: 564,
         8: 520,
         9: 502})

>>> Counter(sampleN() for _ in range(10000))
Counter({0: 984,
         1: 1067,
         2: 1037,
         3: 997,
         4: 957,
         5: 979,
         6: 1030,
         7: 979,
         8: 993,
         9: 977})
НЛО прилетело и опубликовало эту надпись здесь
Господа комментаторы, как вообще можно говорить о применении подобного распределения на практике?
Автор просто взял и свел одно из неслучайных распределений и свел его к равномерному. Вот у 5800 профессоров распределение будет чуть-чуть иным, а если взять распределение цифр от 0 до 9 на куче страниц интернета по любой тематике, то лидировать будет четко единица.
дело ведь в том, что человек нам показал какой-то универсальный алгоритм приведения неслучайных распределений к равномерному с помощью всего двух цифр, не больше и не меньше того.
Не универсальный. Им нельзя привести к равномерному распределение:
1-9: вероятность 0.0001
10: вероятность 0.9991
ну и даже в примере это не равномерное, а близкое к равномерному.

Попросить их пронумероваться. Завязать глаза. Заставить ходить и при столкновении кричать свой номер.

Не ну они должны быть более менее одного диаметра и комплекции )

Статье не хватает опроса «назовите случайное число от 1 до 10» с добавочным вариантом 0.

В статье не хватает двух опросов, на случайные числа.
Насколько равномерно в первом опросе будут распределены выборы?
Насколько распределение ответов во втором опросе будет отличаться от первого?

Почему то, сразу вспомнилось про фон Неймана… Монте-Карло Казино :)… рулетка…

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


А если серьезно, то такая случайность зависит от аудитории. Люди могут сговориться и выдавать все время одно и то же число.

А ещё можно было делать цикличный сдвиг для каждого опрошенного, как остаток от деления на 10, т.е. спросили у 16 по счету человека — сдвинули на 6, спросили у 5673 — сдвинули на 3
Спросили у 5 — сдвинули на 5. Спросили у 10-ого — не сдвигаем?

Ааа, я понял, сорян, сдвигаем результат, а не указатель.
Это даст равномерное количество разных ответов в совокупности. Но каждое число не будет равномерно распределено. Например если все будут отвечать 7, то вы получите результат где каждое число будет встречаться одинаково часто, но при это это все время будет одна и та же циклическая последовательность.
и все равно это выглядит лучше, чем иметь 100% чисел 7, и по нулям — остальных
Узнаём в какой день месяца родился каждый из опрашиваемых.
Для чисел от 1 до 10 и от 11 до 20 записываем, соответственно, 1-10. Числа с 1 по 20 — это два готовых к использования искомых диапазона (1-10). Остальных отбрасываем (банально сокращая выборку), чтобы не ломать голову с 29-31 и равномерным распределением ответов 21-28 между нужными нам 1-10.
Distribution of birthdays by day
Не в тему, просто интересный факт — как-то работал в компании >100 человек, в которой в ноябре ни у кого не было дней рождений.
Можно просто называть количество дней до следующей после дня рождения круглой даты (числа месяца).

Там была прямо противоположная задача: получение перекошенного распределения исходя из равномерного.

Перечитал. Действительно, ошибся
Допустим, у нас действительно есть то самое распределение предпочтений чисел:
 1   3.4%
 2   8.5%
 3  10.0%
 4   9.7%
 5  12.2%
 6   9.8%
 7  28.1%
 8  10.9%
 9   5.4%
10   1.9%
И мистер X выбрал x, а мисс Y выбрала y. Я утверждаю, что этот несложный алгоритм
z = [4, 4, 9, 10, 7, 6, 7, 7, 10, 7, 2, 4, 7, 8, 8, 10, 10, 9, 9, 7, 8,
     1, 4, 9, 8, 10, 3, 10, 3, 4, 5, 6, 1, 5, 8, 8, 9, 7, 7, 9, 3, 2, 3,
     4, 2, 7, 8, 7, 10, 8, 3, 2, 6, 4, 1, 3, 10, 9, 5, 2, 2, 6, 1, 9, 4,
     6, 5, 7, 3, 10, 1, 3, 6, 3, 4, 1, 2, 2, 9, 10, 8, 1, 1, 6, 6, 4, 1,
     8, 2, 5, 6, 6, 3, 5, 4, 1, 2, 6, 2, 10][x * 10 + y - 11]
даст следующее распределение для z:
 1  9.9870%
 2  9.9881%
 3  9.9896%
 4  9.9901%
 5 10.0029%
 6 10.0058%
 7 10.0063%
 8 10.0077%
 9 10.0080%
10 10.0146%
Желающие могут убедиться в этом самостоятельно.

ps Жаль, что с нами нет Бена Торвани (слава богу он не видит эту транскрипцию), уж лучше бы вместо субъективного довольно хороший ГСЧ он выкатил циферки.
Остаток от деления на 10 суммы всех чисел, названных людьми в комнате, уже будет нормализованно распределён. Кто-нибудь, возьмите перекошенное распределение и обработав его таким образом, опровергните это утверждение.
Предположим, что в этой комнате чуть более 8500 студентов.
Зачем же мы будем вас опровергать? Это вы опросите чуть более 8500 студентов и просуммируйте по модулю 10.
А в статье предложили обойтись двумя респондентами.
А откуда автор взял своё распределение? Это он сначала опросил всех студентов в комнате. По результату опроса и сформулировал свою кусочную функцию. В другой комнате, к примеру, китайских студентов, которые не любят число 4, будет другое распределение, и алгоритм должен измениться. Ну, а так-то да, я был невнимателен.
Смотрите, статья вот про что (вы извините меня пожалуйста).
Есть какой-то специфический источник случайных чисел. Ну, например, стоите вы на внешнем периметре Садового кольца (простите, взял для примера), и отмечаете: вот черная машина поехала, вот белая, вот красная, вот вишнёвая, вот зелёная, вот салатовая. А глаз-то у вас — алмаз, что вы видите — то в техпаспарте и записано. А еще у вас в распоряжении вся гаишная база; сколько вишнёвых, сколько салатовых.
Не, у берегов Мичигана другая статистика. Они там все китайские студенты. Но вы-то на внешнем периметре Садового кольца, все дела.
Так понятно, или дать еще интерпретацию?

Выше я привел код и результат

равномерное распределение — это не случайные числа :)
это случайный порядок

Просим людей назвать 0 или 1. Ответ каждого чётного инвертируем. Должны получить равномерное распределение 0 и 1. Берем 6 бит. 0 и больше 10 отбрасываем.

Откуда берётся номер опрошенного?
Опрашивающий инкрементирует регистр у себя в голове
Смотрите, вы написали некий алгоритм из трёх пунктов. Я указал на его неполноту, т.е. некорректность. В ответ вы говорите что-то вроде «а здесь у нас будет волшебная заглушка».
В самой статье тоже расписан алгоритм — это такая выделенная желтым портянка. Не верх изящества, но вполне корректно.
Засада в том, что почти все отметившиеся в коментах портянки не прочли, посыла не поняли, прогнали что-то своё. Если чо — там написано, как, опросив двух человек, получить случайное почти равномерно распределённое число.

"как, опросив двух человек, получить случайное почти равномерно распределённое число"


  1. Опрашиваем всех
  2. Опрашиваем двух человек
  3. Какая-то магия
Тут магия вот какого рода:
  1. нужно прочитать статью
  2. нужно понять прочитанное

Данные об опросе «всех» (некоей «репрезентативной» группы) были взяты откуда-то с Реддита. Потом были сделаны некие допущения, нужные автору, чтобы донести свой замысел. У него, судя по всему, получилось не очень. «Видно, место такое»(с)Жмурки.

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

1. Касательно неполного описания – абсолютно согласен, но и справедливости ради, отмечу, что и в посте не описываются: слышат ли люди друг друга в этой комнате, отсутствуют ли там приверженцы оккультизма, нумерологии и тп. Распределение у разных групп разное.

2. Касательно возможности получить равномерное распределение опрашивая двух человек. Вы же упускаете самое важное – в задаче надо сначала опросить всех в комнате, чтобы получить распределение. А у меня можно этого не делать. И для каждого числа использовать одного опрашиваемого.
Да не существует такой практической задачи — сделать ГСЧ из комнанты с людьми. Это неудачный зачин для статьи — вот и всё. А дальше — код на R и прочий матан.
Если подставить непрерывную случайную величину в свою функцию распределения (строго монотонную), то полученная случайная величина будет распределена равномерно на отрезке [0, 1]. Есть подозрения, что здесь тоже что-то хорошее будет. Например, случайная величина будет с равными вероятности принимать значения p_1,..., p_10, где p_i = p(x <= i).
Представьте, что вам нужно сгенерировать равномерно распределённое случайное число от 1 до 10.

Равномерно распределённое случайное число от 1 до 10 - это что такое? Может имеется в виду генератор чисел? Тогда так и надо писать, а не ввергать в недоумение читателей. Хотя, похоже, на любой вопрос находится ответ и не один.
Надо же, интересно!

Напрашивается какая-то штука наподобие арифметического кодирования.
Берём отрезок [0;1] и нарезаем на 10 равномерных отрезков: [0.0;0.1], [0.1;0.2], ..., [0.9,1.0]
А затем нарезаем его на 10 неравномерных отрезков: [0,p1], [p1,p1+p2], [p1+p2,p1+p2+p3], ...


Если какой-то равномерный отрезок практически совпадает с неравномерным, то при получении цифры "номер неравномерного" выдадим ответ "номер равномерного".


Если в один равномерный отрезок вместилось несколько неравномерных, то при получении любой из цифр "номер неравномерного" среди них, выдадим ответ "номер равномерного".


Наконец, если неравномерный охватывает несколько равномерных (включает целиком или лежит на границе), то разобьём его ещё раз на неравномерные кратно вероятностям.
При назывании цифры "номер этого неравномерного" запросим ещё одну цифру — "номер внутреннего неравномерного" и посмотрим, куда она попала.
Ну и так далее.


Не знаю R, поэтому выражу мысль на питоне.


from math import floor, ceil

def ask():
    v = int(input("товарищ! назови цифру 0..9"))
    assert 0 <= v <= 9
    return v

# распределение называемых цифр
probs = [p1, p2, p3, p4, p5, p6, p7, p8, p9, p10]

sums = [sum(probs[:i]) for i in range(len(probs) + 1)]
assert sums[0] == 0.0
assert sums[10] == 1.0

def random():
    x, y = 0.0, 1.0  # левая и правая границы отрезка на данный момент
    while True:
        dx, dy = floor(x*10), ceil(y*10)
        if dx == dy - 1: return dx  # попали строго в один равномерный отрезок
        w = y - x
        if w < 1e-6: return dx  # ну хватит уже дробить!
        v = ask()
        x, y = x + w * sums[v], x + w * sums[v + 1]  # выбрали подотрезок

Понятно, что алгоритм легко отмасштабировать на произвольное количество называемых и произвольное же количество выдаваемых цифр (например, кидаем равномерный или корявый кубик с 6 гранями, выдаём цифры от 0 до 9). Выходное распределение тоже можно сделать неравномерным.


И посчитать оценки на вероятность количества вопросов на один ответ.

Ваш алгоритм задаёт столько вопросов, сколько ему хочется, в исходной задаче их было два.
А еще он громоздкий (правда и у автора статьи он не маленький). С таким на вечеринке не разгуляешься.
Я думаю, вот отличный алгоритм: спрашиваешь два числа и берешь ответ из таблицы
   |  1  2  3  4  5  6  7  8  9 10
---+-------------------------------
 1 |  8  4 10  7 10  9  3  9  5  2
 2 |  1  7  4  8  7  6  7 10  8  8
 3 |  6  2  3  9  2 10  9 10  8 10
 4 |  3  8  5  9  3  7 10  5  7  7
 5 |  4  1  1  1  2  9  8  5  8  8
 6 |  5  1  2  5  4  4  7  9  6  9
 7 |  1  3  2 10  1  3  6  5  9  5
 8 |  5  8  7  4  4  2  4  5 10  2
 9 |  4  2  2  3  3  1  8  9  2  8
10 |  1  6  8  6  1  3  4  1  4  6

Если верить исходной статистике (а ей верить нельзя, там сумма по всем числам 99.9%, ну да я отнормировал), вероятности чисел из таблицы лежат в интервале 9.9987% ~ 10.0013%.
Хех, хоть бы кто проверить удосужился )

Ну делов-то, ограничить число попыток двумя, а не отсечкой по заданной точности.


А вообще, с двумя попытками похоже на задачу об упаковке рюкзака.
Пусть у нас есть распределение P(d)={p0,p1,p2,...,p9}
Делаем из него распределение двух попыток Q(ab)={qab = pa*pb}
и затем пытаемся разбить на более-менее равные суммы: {s0={qij+qkl+...}, s1={...}, ..., s9}


У этой задачи нет решения в общем случае.
Какое-нибудь жестачайше неравномерное распределение, при котором разбивание на произвольные суммы сведётся к моему решению, а там на второй итерации точность не сильно улучшится.
Например, {0.991, 0.001*9}
Декартово произведение даст набор {0.982081, 0.00991*9, 0.00001*90}
Тут как хочешь, но сделать десять сумм, примерно равных 0.1, не получится. Одна сумма будет примерно 0.98, все остальные уложатся в оставшееся 0.02
Чтобы получить суммы, примерно равные 0.1 хотя бы с точностью до одного знака, надо сделать до 245 вопросов! (0.991**244 = 0.1101..., 0.991**245 = 0.1091...)




Не знаю, что вы вкладываете в понятие "громоздкий", если табличка там всего из 10 элементов, а в цикле всего два умножения, два обращения к таблице и два сложения.


Тогда как ваше табличное решение требует уже 100-элементную таблицу (для двух вопросов; для трёх — соответственно, 1000-элементную) и какой-то лютый препроцессинг, возможно, NP-полный, и, как показано выше, не всегда выполнимый.

У этой задачи нет решения в общем случае
Её стоит переформулировать — дать наилучшее решение по какому-нибудь критерию: мин.дисперсия, мин.отрезок, в который укладываются выходные вероятности и т.п.
с двумя попытками похоже на задачу об упаковке рюкзака /далее по тексту/
Именно.
что вы вкладываете в понятие «громоздкий»
Да это так, шутка: никто, включая автора, не озаботился снабдить полевых исследователей алгоритмом, с которым бы они управились на вечеринке. А с табличкой и пьяный справится )
какой-то лютый препроцессинг, возможно, NP-полный
NP-полный я не потянул. Допилил одну эвристику:
from heapq import heappop, heappush, heappushpop
from collections import defaultdict
from itertools import product
from random import random

N = 2  # сколько человек опрашивать
data = [random() for _ in range(10)]  # ну не [0.991, 0.001,...] же совать:
total = sum(data)
data = sorted(p / total for p in data)  # нормирую и для красоты сортирую
heap, p2ij, = [], defaultdict(set)
for ij in product(range(10), repeat=N):
    p = -1.
    for i in ij:
        p *= data[i]
    heappush(heap, [p, [p], *[[] for _ in range(9)]])
    p2ij[p].add(ij)

bags = heap.pop()
while heap:
    bags = sorted(heappushpop(heap, bags)[1:] + heappop(heap)[1:], key=sum)
    for i in range(10):
        bags[i] += bags.pop()
    bags.sort(key=sum)
    bags.insert(0, sum(bags[0]) - sum(bags[-1]))

tbl = {}
print(f'     % для     % для {N}\n     одного    по таблице')
for i, rnd, bag in zip(range(10), data, bags[::-1]):
    print(f'{i}:{rnd * 1e2:>9.4f} {sum(bag) * -1e2:>9.4f}')
    for p in bag:
        tbl[p2ij[p].pop()] = i
if N == 2:
    print('\nа вот таблица:\n')
    for i in range(10):
        print(*[tbl[i, j] for j in range(10)], sep='  ')
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории