Это просто перебор методом «тыка», но с заумным названием.
… можно показать, что если бы мы рассмотрели все объекты определённого типа, и затем выбрали один из них случайным образом, то существует ненулевой шанс выбрать объект с нужным свойствам.
Никуда тыкать не надо — сам факт ненулевой вероятности и является доказательством существования «объекта с нужным свойствам».
Ваш подход с мерой действительно прямее, но дело в том, что аппарат теорвера повсеместно освоен и им зачастую сподручней выразить мысль.
На эту тему (в том числе про Эрдёша) есть отличные лекции Райгородского, например.
Её стоит переформулировать — дать наилучшее решение по какому-нибудь критерию: мин.дисперсия, мин.отрезок, в который укладываются выходные вероятности и т.п.
с двумя попытками похоже на задачу об упаковке рюкзака /далее по тексту/
Именно.
что вы вкладываете в понятие «громоздкий»
Да это так, шутка: никто, включая автора, не озаботился снабдить полевых исследователей алгоритмом, с которым бы они управились на вечеринке. А с табличкой и пьяный справится )
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=' ')
Какой смысл? Последнее число Фибоначчи, влезающее в свифтовский UInt64 — это №90, 0xa94fad42221f2702, оно дербанится в 90 итераций любым способом. Что тут мерять-то?
Ваш алгоритм задаёт столько вопросов, сколько ему хочется, в исходной задаче их было два.
А еще он громоздкий (правда и у автора статьи он не маленький). С таким на вечеринке не разгуляешься.
Я думаю, вот отличный алгоритм: спрашиваешь два числа и берешь ответ из таблицы
Если верить исходной статистике (а ей верить нельзя, там сумма по всем числам 99.9%, ну да я отнормировал), вероятности чисел из таблицы лежат в интервале 9.9987% ~ 10.0013%.
Хех, хоть бы кто проверить удосужился )
Да не существует такой практической задачи — сделать ГСЧ из комнанты с людьми. Это неудачный зачин для статьи — вот и всё. А дальше — код на R и прочий матан.
Данные об опросе «всех» (некоей «репрезентативной» группы) были взяты откуда-то с Реддита. Потом были сделаны некие допущения, нужные автору, чтобы донести свой замысел. У него, судя по всему, получилось не очень. «Видно, место такое»(с)Жмурки.
Идея автора была в том, что из неравномерного дискретного распределения с маленьким базисом (всего 10 чисел) в полпинка можно породить равномерное. Он показал как это сделать технически и сделал клёвую иконографику.
Смотрите, статья вот про что (вы извините меня пожалуйста).
Есть какой-то специфический источник случайных чисел. Ну, например, стоите вы на внешнем периметре Садового кольца (простите, взял для примера), и отмечаете: вот черная машина поехала, вот белая, вот красная, вот вишнёвая, вот зелёная, вот салатовая. А глаз-то у вас — алмаз, что вы видите — то в техпаспарте и записано. А еще у вас в распоряжении вся гаишная база; сколько вишнёвых, сколько салатовых.
Не, у берегов Мичигана другая статистика. Они там все китайские студенты. Но вы-то на внешнем периметре Садового кольца, все дела.
Так понятно, или дать еще интерпретацию?
Смотрите, вы написали некий алгоритм из трёх пунктов. Я указал на его неполноту, т.е. некорректность. В ответ вы говорите что-то вроде «а здесь у нас будет волшебная заглушка».
В самой статье тоже расписан алгоритм — это такая выделенная желтым портянка. Не верх изящества, но вполне корректно.
Засада в том, что почти все отметившиеся в коментах портянки не прочли, посыла не поняли, прогнали что-то своё. Если чо — там написано, как, опросив двух человек, получить случайное почти равномерно распределённое число.
Предположим, что в этой комнате чуть более 8500 студентов.
Зачем же мы будем вас опровергать? Это вы опросите чуть более 8500 студентов и просуммируйте по модулю 10.
А в статье предложили обойтись двумя респондентами.
ps Жаль, что с нами нет Бена Торвани (слава богу он не видит эту транскрипцию), уж лучше бы вместо субъективного довольно хороший ГСЧ он выкатил циферки.
На эту тему (в том числе про Эрдёша) есть отличные лекции Райгородского, например.
Именно.
Да это так, шутка: никто, включая автора, не озаботился снабдить полевых исследователей алгоритмом, с которым бы они управились на вечеринке. А с табличкой и пьяный справится )
NP-полный я не потянул. Допилил одну эвристику:
0xa94fad42221f2702, оно дербанится в 90 итераций любым способом. Что тут мерять-то?А еще он громоздкий (правда и у автора статьи он не маленький). С таким на вечеринке не разгуляешься.
Я думаю, вот отличный алгоритм: спрашиваешь два числа и берешь ответ из таблицы
Если верить исходной статистике (а ей верить нельзя, там сумма по всем числам 99.9%, ну да я отнормировал), вероятности чисел из таблицы лежат в интервале 9.9987% ~ 10.0013%.
Хех, хоть бы кто проверить удосужился )
Данные об опросе «всех» (некоей «репрезентативной» группы) были взяты откуда-то с Реддита. Потом были сделаны некие допущения, нужные автору, чтобы донести свой замысел. У него, судя по всему, получилось не очень. «Видно, место такое»(с)Жмурки.
Идея автора была в том, что из неравномерного дискретного распределения с маленьким базисом (всего 10 чисел) в полпинка можно породить равномерное. Он показал как это сделать технически и сделал клёвую иконографику.
Есть какой-то специфический источник случайных чисел. Ну, например, стоите вы на внешнем периметре Садового кольца (простите, взял для примера), и отмечаете: вот черная машина поехала, вот белая, вот красная, вот вишнёвая, вот зелёная, вот салатовая. А глаз-то у вас — алмаз, что вы видите — то в техпаспарте и записано. А еще у вас в распоряжении вся гаишная база; сколько вишнёвых, сколько салатовых.
Не, у берегов Мичигана другая статистика. Они там все китайские студенты. Но вы-то на внешнем периметре Садового кольца, все дела.
Так понятно, или дать еще интерпретацию?
В самой статье тоже расписан алгоритм — это такая выделенная желтым портянка. Не верх изящества, но вполне корректно.
Засада в том, что почти все отметившиеся в коментах портянки не прочли, посыла не поняли, прогнали что-то своё. Если чо — там написано, как, опросив двух человек, получить случайное почти равномерно распределённое число.
А в статье предложили обойтись двумя респондентами.
даст следующее распределение для z:
Желающие могут убедиться в этом самостоятельно.
ps Жаль, что с нами нет Бена Торвани (слава богу он не видит эту транскрипцию), уж лучше бы вместо субъективного довольно хороший ГСЧ он выкатил циферки.
буклетмусор, хотя кому они там рекламируют? Родной компартии — тогда зачем по-английски?И спорить с вами не буду — вы вишь какой умный.
Если бы я сделал то, что вы мне приписываете, я бы сделал это так:Улавливаете разницу?
На самом деле я обратился к экземпляру класса: поищи-ка у себя что-то по имени
format. И он (экземпляр класса) таки нашел у себя метод с этим именем.И да: если не улавливаете — не утруждайте себя ответом.
Зачем же так подставляться? Когда надо — они кое-что знают:
Это шизофазия?