Выберите случайное число от 0 до n, используя постоянный источник случайности

26

задача

Если положительное целое число nменьше 2^30указанного в качестве входного значения любым выбранным вами способом, ваш код должен выдавать случайное целое число между 0и nвключительно. Число, которое вы генерируете, должно выбираться случайным образом равномерно . То есть каждое значение от 0до nдолжно происходить с равной вероятностью (см. Правила и предостережения).

Правила и предостережения

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

  • Вы должны установить, что если используемый вами случайный источник является однородным, то ваш код правильно выводит равномерное случайное целое число из 0в n.
  • Любые аргументы при вызове встроенной или библиотечной случайной функции должны быть постоянными. То есть они должны быть полностью независимы от входного значения.
  • Ваш код может завершиться с вероятностью 1, а не гарантированно завершить.

Заметки

  • randInt(0,n) недопустимо, поскольку принимает входные данные в качестве аргумента встроенной или библиотечной функции.
  • rand()%nне будет давать равномерное случайное число в целом. В качестве примера, приведенного Betseg, если intmax == 15и n = 10, то вы будете иметь гораздо больше шансов, 0-5чем 6-10.
  • floor(randomfloat()*(n+1)) также не будет давать равномерное случайное число в целом из-за конечного числа различных возможных значений с плавающей запятой между 0 и 1.
totallyhuman
источник
Как вы собираетесь подтвердить, что выходные данные равномерно случайны? Может быть так, что данный язык / библиотека будет выводить равномерно случайные числа, но манипулирование может привести к неравномерному выводу. (например, rng()обеспечивает 0- 100, если n = 75и функция есть rng()%75, то 0-25 будет более распространенным ...)
Baldrickk
1
@Baldrickk По мудрости толпы :) Мы можем только читать код и думать об этом.
Печальный вывод вопроса о простейшем из теории вероятностей: случайность и вероятность очень плохо поняты. :( (И читать правила трудно, по-видимому.)
Мартин Эндер
Это приходит на ум: Случайное число
BgrWorker
Почему вы приняли ответ x86, когда есть три более коротких?
Деннис

Ответы:

25

x86 машины с rdrandинструкцией, 10 байт

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

Машинный код

0FC7F0 73FB 39F8 77F7 C3

Вход находится в регистре, rdiа выход - в rax.
Это учитывает SYS V AMD64 ABI, поэтому код эффективно реализует функцию C

unsigned int foo(unsigned int max); 

с 32-битным целым

Инструкция rdrandописана Intel

RDRANDвозвращает случайные числа, предоставленные криптографически безопасным, детерминированным генератором случайных битов DRBG. DRBG разработан в соответствии со стандартом NIST SP 800-90A .

Имея дело с CSRNG, подразумевается, что распределение является однородным, в любом случае, цитируя NIST SP 800-90A:

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


Процедура генерирует случайное число и, если оно не строго больше, чем входное значение, оно возвращается.
В противном случае процесс повторяется.

Поскольку он eaxявляется 32-битным, rdrandвозвращает число от 0 до 2 32 -1, поэтому для каждого n в [0, 2 32 -1] число ожидаемых итераций равно 2 32 / (n + 1), которое определено для всех n в [0, 2 30 ).

Маргарет Блум
источник
Блестяще низкий уровень. Спасибо.
Для чего jnc?
l4m2
@ l4m2 rdrandустанавливает, вернут ли CFверные данные. Данные могут быть недействительными, потому что слишком много запросов истощило пул энтропии. Смотрите руководство для rdrand и это .
Маргарет Блум
20

Желе , 7 6 байт

⁴!!X%‘

Спасибо @JonathanAllan за отыгрывание 1 байта!

Не может быть запущен на TIO, потому что (16!)! это огромное количество.

Как это работает

⁴!!X%‘  Main link. Argument: n

⁴       Set the return value to 16.
 !!     Compute (16!)!.
   X    Pseudo-randomly choose an integer between 1 and (16!)!.
        Since (16!)! is evenly divisible by any k ≤ 2**30, it is evenly divisible
        by n+1.
    %‘  Take the result modulo n+1.
Деннис
источник
Это исправленная версия моего удаленного ответа, та же идея. Хотя у меня действительно было ненужное возведение в степень.
17
Извините, я не смотрел на это перед публикацией.
Деннис
О, это не имеет значения, я все равно не планировал это чинить. Мне слишком неудобно с Джелли, чтобы по-настоящему поиграть с этим.
17
1
«Сэр, я не знаю, почему вы злитесь. Алгоритм - это постоянное время. Это хорошо, правда? Почему безопасность и HR за дверью?»
CorsiKa
1
Согласовано. Разница между 8-значным и 417-квинтиллионным номером: p
Джонатан Аллан
11

Mathematica, 29 байт

Основано на ответе желе Денниса .

RandomInteger[2*^9!-1]~Mod~#&

Я бы не рекомендовал на самом деле запустить это. 2e9!это довольно большое число ...

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

Отбор выборки, 34 байта

Мой старый подход, который привел к несколько более интересному коду:

13!//.x_/;x>#:>RandomInteger[13!]&

Основная отбраковочная выборка. Мы инициализируем вывод 13! (который больше, чем максимальный вход 2 30 ), а затем несколько раз заменить его случайным целым числом от 0 до 13! до тех пор, пока значение больше, чем вход.

Мартин Эндер
источник
1
Вы имеете в виду «меньше или равно входу»?
1
@Lembik Нет. Мы хотим восстановить значение, если оно не попадает в нужный диапазон.
Мартин Эндер
А ну понятно. По какой-то причине я думал, что мы неоднократно брали образцы из желаемого диапазона. Спасибо.
1
Напомни мне добавить ограничение по времени в следующий раз :)
9

Брахилог , 9 байт

≥.∧13ḟṙ|↰

Попробуйте онлайн!

Это использует, 13!как в ответе Мартина Эндера ( 13ḟна один байт меньше 2^₃₀).

реализуется с использованием random_between/3, которое при копании своего источника использует то, с random_float/0чем связано, и random/1использует алгоритм Мерсенна Твистера, который является единым для наших целей.

объяснение

≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input
Fatalize
источник
7

Пролог (SWI) , 38 байт

X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.

Работает методом отбраковки.

Генерируйте случайное число от 0 до 2 ^ 31-1 = 2147483647 до тех пор, пока не будет найдено одно значение, меньшее или равное входному значению.

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

Emigna
источник
1
Вы могли бы избежать использования остального repeat, но в итоге получилось бы на 3 байта длиннее ... Я не уверен, что есть более короткий способ иметь бесконечные точки выбора, чем повторение.
Роковая
@Fatalize: Да, я тоже пытался повторить. У меня было воспоминание об использовании чего-то вроде ,!.принудительного возврата, но либо я помню это неправильно, либо это не применимо к этому решению.
Emigna
7

Лабиринт , 63 байта

 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#

(Спасибо @MartinEnder за помощь в игре в гольф)

Лабиринт - это двумерный язык, и его единственным источником случайности является ситуация, подобная следующей:

   x
  "<)
 " "
 " "

Предположим, указатель инструкции находится на xи движется вниз. Затем он попадает на <, который, если вершина стека равна 0 (что всегда имеет место в реальной программе выше), сдвигает текущую строку влево на 1:

   "
 "<)
 " "
 " "

Указатель инструкции теперь <движется вниз. На перекрестке Лабиринт поворачивается в зависимости от вершины стека - отрицательный - поворот влево, положительный - поворот вправо, а ноль - движение вперед. Если в этом месте вершина стека все еще равна нулю, мы не можем двигаться вперед или назад, поскольку пути нет, поэтому Лабиринт будет случайным образом поворачивать налево или поворачивать направо с равной вероятностью.

По сути, вышеприведенная программа использует функцию случайности для генерации 100-битных чисел ( #00здесь указано 100 ) и продолжает цикл до тех пор, пока он не сгенерирует число <= n.

Для тестирования, вероятно, будет полезно использовать #0"вместо этого для 10-битных чисел, с тем, "чтобы быть неоперативным путем. Попробуйте онлайн!

Грубое объяснение:

 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#

 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.
Sp3000
источник
7

Python, 61 байт

from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)

Изменить: Обновлено, чтобы избежать запрещенной формы

Edit2: сохранено 2 байта, спасибо @ JonathanAllan

Edit3: заплатил 2 байта за полнофункциональное решение - еще раз спасибо @JonathanAllan

Edit4: удалено f=, сохранение 2 байта

Edit5: еще 1 байт благодаря @ JonathanAllan

Edit6: сохранено еще 2 байта благодаря @ JonathanAllan

К настоящему моменту, мерзавец обвиняет меня в плохих вещах, а Джонатан Аллан - в том, что помогает.

Edit7: когда идет дождь, он льет - еще 2 байта

Edit8: и еще 2 байта

iwaseatenbyagrue
источник
1
Это никогда не будет выводиться n, но вы можете сохранить два байта, когда исправите это, используя from random import*и удаляя r..
Джонатан Аллан
1
Да, вы можете использовать «оператор головастика», чтобы избежать других необходимых круглых скобок, ...*(-~n*1.0/2**30))а не...*((n+1)*1.0/2**30))
Джонатан Аллан
1
В самом деле? Милая! У вас есть давняя обида на номер 70? Большое спасибо за вашу помощь
iwaseatenbyagrue
1
На самом деле, randrangeкажется, принимает поплавок, поэтому lambda n,x=2.**30:int(randrange(x)*-~n/x)сохраняет еще две [править ...] четыре!
Джонатан Аллан
1
^ еще два там с удалением скобок. Просто идет, чтобы показать, что ваше умножение было способом!
Джонатан Аллан
6

Python 2 , 61 байт

from random import*
lambda n:map(randrange,range(1,2**31))[n]

Псевдослучайно выбирает целые числа между 0 и k для всех значений k между 0 и 2 31 - 2 , затем принимает целое число, соответствующее k = n .

Деннис
источник
5

Пакетная, 64 байта

@set/ar=%random%*32768+%random%
@if %r% gtr %1 %0 %1
@echo %r%

%random%дает только 15 бит случайности, поэтому я должен объединить два случайных числа. Цикл до тех пор, пока случайное значение не окажется в желаемом диапазоне, поэтому медленно для низкого уровня n; 98 байт для более быстрой версии:

@set/a"n=%1+1,m=~(3<<30)/n*n,r=%random%*32768+%random%
@if %r% geq %m% %0 %1
@cmd/cset/a%r%%%%n%
Нил
источник
Код может быть медленным, но ваш ответ был быстрым!
3
@Lembik У меня был готов ответ на удаленный вопрос ...
Нил
Не будет ли это отражать сначала нужное число, а затем все остальные числа, которые оказались больше n?
Эрик Outgolfer
@EriktheOutgolfer Нет; если вы не используете call, вызов пакетного сценария завершает текущий сценарий.
Нил
5

MATL , 12 байт

Благодаря @AdmBorkBork и к @Suever рассказал мне , как отключить кэш TIO.

`30WYrqG>}2M

Попробуйте онлайн! ,

При этом используется метод отклонения : генерировать случайное целое число из 0в 2^30-1и повторять, пока оно превышает входные данные n. Это гарантированно завершится с вероятностью 1, но среднее число итераций равно 2^30/n, и поэтому это занимает очень много времени nзначительно меньше, чем 2^30.

`         % Do...while
  30W     %   Push 2^30
  Yr      %   Random integer from 1 to 2^30
  q       %   Subtract 1
  G>      %   Does it exceed the input? If so: next iteration. Else: exit
}         % Finally (execute right before exiting the loop)
  2M      %   Push the last generated integer
          % End (implicit). Display (implicit)
Луис Мендо
источник
4

JavaScript (ES6), 55 54 байта

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

Генерирует целые числа в диапазоне [0 ... 2 k - 1] , где k - наименьшее целое число, такое, что 2 k больше, чем n . Повторяется до тех пор, пока результат не попадет в [0 ... n] .

Зачем?

Это основано на следующих предположениях:

  • Внутри псевдослучайные целочисленные значения, генерируемые механизмом JS для подачи, Math.random()являются однородными в течение любого интервала [0 ... 2 k -1]k <32 ).

  • После умножения на точную степень 2 возвращаемые значения с плавающей точкой IEEE 754 Math.random()остаются одинаковыми в течение таких интервалов.

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

демонстрация

Создает 1 миллион значений в [0 ... 2] и отображает статистику результатов.

Arnauld
источник
Math.floor (Math.random () * (n + 1)) дает не менее равномерно распределенные результаты для меня, поэтому было бы неплохо увидеть, существует ли какой-либо реалистичный N <2 ^ 30, который будет вызывать какие-либо аномалии распределения вообще.
Цеппелин
1
@zeppelin вам понадобится слишком много пробных запусков, чтобы точно определить любые аномалии, поскольку случайное смещение в этом диапазоне будет иметь одно из 2 ^ 53 значений, которое будет распределено как можно более равномерно по 2 ^ 30 результатам. Так что даже для больших чисел в диапазоне ошибка будет примерно равна 1 в 2 ^ 23, что означает, что вам понадобится нелепое количество испытаний. Вы, вероятно, захотите на несколько порядков больше, чем количество исходных выборок (2 ^ 53). Тем не менее, он не может быть совершенно равномерным, если множитель не делит поровну количество выборок, поэтому Арно использует степень два.
Мартин Эндер
4

Bash (+ coreutils), 44 байта

/ dev / решение на основе urandom

od -w4 -vtu4</d*/ur*|awk '($0=$2)<='$1|sed q

Считает 32-разрядные целые числа без знака /dev/urandomи отфильтрует их, awkпока не найдет одно в заданном диапазоне, а затем sed qпрервет конвейер.

дирижабль
источник
Ура для bash :)
4

Haskell, 70 байт

import System.Random
g n=head.filter(<=n).randomRs(0,2^30)<$>getStdGen

Не очень эффективный алгоритм, но он работает. Он генерирует бесконечный список целых чисел (или, если необходимо, с плавающей точкой, из-за системы типов Хаскелла), ограниченный [0,2 ^ 30], и принимает первое, меньшее или равное n. Для малых русских это может занять много времени. Случайные числа должны быть равномерно распределены, как указано в документации для randomR, поэтому все числа в интервале [0,2 ^ 30] должны иметь одинаковую вероятность (1 / (2 ^ 30 + 1)), поэтому все числа в [ 0, n] имеют одинаковую вероятность.

Альтернативная версия:

import System.Random
g n=head.filter(<=n).map abs.randoms<$>getStdGen

Эта версия ужасна, но сохраняет целый байт. randomsиспользует произвольный диапазон, определенный типом, чтобы генерировать бесконечный список чисел. Это может включать в себя негативы, поэтому нам нужно сопоставить его с absположительным значением (или нулем). Это очень медленно для любых значений n, которые не являются абсурдно большими. РЕДАКТИРОВАТЬ : я понял позже, что эта версия не распределена равномерно, потому что вероятность получения 0 хуже, чем другие числа из-за использования abs. Для того, чтобы произвести некоторое количество mгенератора может производить mили , -mно в случае 0 0 только сам будет работать, поэтому его вероятность равна половина остальных чисел.

user1472751
источник
Ура для Хаскелла (тоже)!
4

Желе , 9 байт

⁴!Ẋ’>Ðḟ⁸Ṫ

Попробуйте онлайн! - код выше не будет работать на TIO, поскольку диапазон размера 16! сначала должен быть построен (не говоря уже о том, что их затем нужно перетасовать, а затем отфильтровать!), так что это то же самое в гораздо меньшем масштабе, повторяется 30 раз для входа 3 с пределом 10.

Как?

⁴!Ẋ’>Ðḟ⁸Ṫ - Main link: n
⁴         - 16
 !        - factorial: 20922789888000
  Ẋ       - shuffle random: builds a list of the integers 1 through to 16! inclusive and
          - returns a random permutation via Python's random.shuffle (pretty resource hungry)
   ’      - decrement (vectorises - a whole pass of this huge list!)
     Ðḟ   - filter out if: (yep, yet another pass of this huge list!)
    >     -     greater than
       ⁸  -     left argument, n
        Ṫ - tail: return the rightmost remaining entry.

Примечание: было бы более чем в тысячу раз эффективнее для того же подсчета байтов, если ȷ⁵бы он делал то, что наивно ожидал, и возвращал бы десять к десяти, но это не так, поскольку не оценивается как буквальная десятка, которая будет использоваться по ȷ...числовому литералу, а вместо этого анализируются два отдельных литерала, ȷпричем его показатель по умолчанию равен трем, что дает тысячу, а дает десять.

Джонатан Аллан
источник
Да, это 9 символов, но 22 байта
Кристоффер Салл-Сторгард
@ KristofferSall-Storgaard Каждый символ - это один из 256 байтов в кодовой странице Jelly , я забыл сделать ссылку на байты слова, как обычно.
Джонатан Аллан
1
год, я посмотрел его и узнал то же самое
Кристоффер Салл-Сторгард
4

JDK 9 на jshell, 75 59 байт

n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny()

использование

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 байт: спасибо, Джейкоб!
  • Предполагается, что мы считаем jshell допустимой средой выполнения.
  • Сам jshell, как среда выполнения, не требует явного импорта основных библиотек и не требует точек с запятой.
  • Возвращает OptionalInt. Правила не указывают, что возвращаемый тип должен быть примитивным, и я считаю, OptionalIntчто допустимое представление результата.
Пит Терлеп
источник
1
Спасибо @ kevin-cruijssen за вдохновение. Мой первый код гольф!
Пит
Принято ли в штучной упаковке вывод, отличается от того, Optionalпринято ли. Я бы подтвердил с плакатом на вашем месте. Кроме того, нет необходимости считать все назначение; достаточно лямбда-выражения.
Якоб
1
Вы можете сохранить 4 байта, удалив скобки вокруг параметра лямбда nи new Random().
Якоб
3

PHP, 30 байт

    while($argn<$n=rand());echo$n;

Беги с echo <N> | php -Rn '<code>'.

выбирает случайное число от 0 до getrandmax()(2 ** 31-1 на моей 64-битной машине);
повторяется, пока это больше, чем вход.

Это может занять некоторое время ... моему AMD C-50 (1 ГГц) потребовалось от 0,3 до 130 секунд N=15.

Более быстрый способ для среднего N( 46 байт ):

for(;++$i<$x=1+$argn;)$n+=rand()%$x;echo$n%$x;

или

for(;++$i<$x=1+$argn;$n%=$x)$n+=rand();echo$n;

берет N+1случайные целые числа, суммирует их и принимает по модулю N+1.
C-50 нуждается в ок. 8 секунд на 1 миллион пробежек.

Неверное решение для 19 байтов :

echo rand(0,$argn);
Titus
источник
3

PowerShell , 35 байт

for(;($a=Random 1gb)-gt"$args"){}$a

Попробуйте онлайн!

Еще один метод отбора проб отклонения. Это бесконечный forцикл, устанавливая значение , $aчтобы быть Randomцелое число между 0и 1gb( = 1073741824 = 2^30), и продолжает цикл до тех пор, что является целым числом -gля большей tхань вход $args. Когда цикл завершен, мы просто включаем $aконвейер и вывод неявен.

Примечание. Это займет много времени, если введено небольшое число.

AdmBorkBork
источник
3

Python 2 , 72 69 байт

-3 байта благодаря xnor (переопределить idвстроенную переменную)

from random import*
n=input()
while id>n:id=randrange(2**30)
print id

Попробуйте онлайн!

randrange(2**30)производит псевдо-равномерно распределенное число (Mersenne Twister 2 19937-1 ) из диапазона [0,2 30 ) . Так nкак гарантированно будет меньше 2 30, это можно просто вызывать повторно, пока оно не будет больше, чем вход. Ожидается, что для очень низких значений потребуется долгое время n, но обычно он работает в течение одной минуты, даже для входов, таких как 50.

Джонатан Аллан
источник
2
Вы можете инициализировать r=''как «бесконечность». Или, что еще лучше, не инициализируйте rи вместо этого используйте idвезде r.
xnor
2

05AB1E , 11 байт

žIÝ.rDI›_Ϥ

Попробуйте онлайн!

объяснение

žIÝ          # push the inclusive range [0 ... 2^31]
   .r        # get a random permutation (pythons random.shuffle)
     D       # duplicate this list
      I      # push input
       ›_Ï   # keep only elements from the list not greater than input
          ¤  # take the last one

Поскольку список [0 ... 2147483648]слишком велик для TIO, 1.000.000вместо него используется ссылка .

Альтернативное (в среднем) намного более быстрое 11-байтовое решение

[žIÝ.RD¹›_#

Попробуйте онлайн

объяснение

[             # start loop
 žIÝ          # push the inclusive range [0 ... 2^31]
    .R        # pick a random integer (pythons random.chiose)
      D       # duplicate
       ¹      # push input
        ›_#   # break if random number is not greater than input
              # implicitly output top of stack (the random number)
Emigna
источник
žJL.R%на 6, если я не пропустил что-то огромное. Нажмите 2 ^ 32, список от 0 до 2 ^ 32, случайный выбор. Модуль ввода. Будет абсолютно ввернуть эффективность, которая у вас есть.
Волшебный осьминог Урна
@ carusocomputing. Вам нужно I7 байт, чтобы получить аргументы для модуля в правильном порядке (и, возможно, Ýвместо L), но в остальном это, безусловно, более короткое решение. Я видел, как Деннис делал это в своем ответе на желе, но так как это была моя первая идея, я сохранил это. Поскольку этот подход отличается от этого, вы можете опубликовать его как отдельный ответ.
Emigna
DI‹Ïбы избежать петли.
Волшебный осьминог Urn
Кроме того, как есть, это не гарантируется, чтобы прекратить; если я не ошибаюсь, ввод 0почти всегда приводит к почти бесконечному циклу, что затрудняет завершение. Хотя решение допускает возможность завершения во всех сценариях, оно не гарантируется из-за случайности.
Волшебный Осьминог Урна
@carusocomputing: При очень маленьком вводе вторая версия в среднем может занять очень много времени, чтобы закончить да, но при наличии достаточного времени.
Emigna
2

Python 2, 89 байт

l=range(2**31)
import random
random.shuffle(l)
n=input()
print filter(lambda x:x<=n,l)[0]

объяснение

L=range(2**31)      # Create a list from 0 to 2^31 exclusive. Call it <L>.
import random       # Import the module <random>.
random.shuffle(L)   # Use 'shuffle' function from <random> module,
                    # to shuffle the list <L>.
n=input()           # Take the input -> <n>.

print
    filter(         # Create a new sequence,
    lambda x:x<=n   # where each element is less than or equal to <n>.
    ,L)             # from the list <L>.
    [0]             # Take the first element.

Это очень неэффективно, так как создает 2 ^ 31 целых чисел, перемешивает и фильтрует их.

Я не вижу смысла делиться ссылкой TIO, где создаются такие большие списки, поэтому здесь ссылка TIO для n= 100.

Попробуйте онлайн!

Yytsi
источник
2

Java 8, 84 83 80 71 62 байта

n->{int r;for(;(r=(int)(Math.random()*(1<<30)))>n;);return r;}

-1 байт благодаря @ OliverGrégoire .
-3 байта благодаря @Jakob .
-9 байтов, преобразующих Java 7 в Java 8.
-9 байтов путем изменения java.util.Random().nextInt(1<<30)на (int)(Math.random()*(1<<30)).

Объяснение:

Попробуй это здесь.

n->{        // Method with integer parameter and integer return-type
  int r;    //  Result-integer
  for(;(r=(int)(Math.random()*(1<<30)))>n;);
            //  Loop as long as the random integer is larger than the input
            //  (the random integer is in the range of 0 - 1,073,741,824 (2^30))
  return r; //  Return the random integer that is within specified range
}           // End method

ПРИМЕЧАНИЕ. Очевидно, что для небольших входов может потребоваться очень много времени.

Пример вывода:

407594936
Кевин Круйссен
источник
2
@ Аарон Я тоже подверг сомнению это, но вижу второй пункт: «Любые аргументы при вызове встроенной или библиотечной случайной функции должны быть постоянными. То есть они должны быть полностью независимы от входного значения». Это причина, по которой используется max int.
Poke
1
2^30= 1073741824. Вы предпочли использовать -1>>>1(= 2147483647). Но это существует: 1<<30что в точности равно 2^30; и на 1 байт короче.
Оливье Грегуар
1
Как насчет int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}?
Якоб
@ Якоб Спасибо. Я даже сократил его на 18 байт, используя Java 8 вместо 7 и используя Math.random()вместо java.util.Random().nextInt.
Кевин Круйссен
2

Python 3, 51 байт

Вот Python-решение с неортодоксальным случайным источником.

print(list(set(map(str,range(int(input())+1))))[0])

Попробуйте онлайн!

Так что, чтобы сломать это.

int(input())+1

Получает входной номер и добавляет 1к нему.

set(range(...))

Создает набор {0, 1, 2, 3, 4, ... n}для всех возможных результатов.

print(list(...)[0])

Берет набор, преобразует его в список и берет первый элемент.

Это работает, потому что в Python 3 порядок set()устанавливается PYTHONHASHSEED ( не может быть получен, но устанавливается при выполнении скрипта).

Правда, я предполагаю, что это равномерное распределение, так как hash()значение назначается случайным образом, и я смотрю на случайный выбор значения с определенным значением hash(), а не просто на возврат самого hash(input())себя.

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

Мэтт
источник
1

C #, 57 байт

n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

Анонимная функция, которая возвращает целое число от 0 до n включительно.

Чем меньше введенное число, тем дольше время для возврата случайного значения.

Полная программа:

using System;

class RandomNumber
{
    static void Main()
    {
        Func<int, int> f =
        n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

        // example
        Console.WriteLine(f(100000));
    }
}
adrianmp
источник
2
«Любые аргументы при вызове встроенной или библиотечной случайной функции должны быть постоянными. То есть они должны быть полностью независимы от входного значения». Аргумент к Nextне является статичным.
Yytsi
1

Bash + coreutils, 20 байтов

Golfed

seq 0 $ 1 | shuf | sed 1q

shuf - генерировать случайные перестановки

Шуф будет использовать следующий код : для генерации перестановок:

permutation = randperm_new (randint_source, head_lines, n_lines);

который заканчивается в randint_genmax

/* Consume random data from *S to generate a random number in the range
0 .. GENMAX.  */

randint
randint_genmax (struct randint_source *s, randint genmax) 
{
      ...

      randread (source, buf, i);

      /* Increase RANDMAX by appending random bytes to RANDNUM and
         UCHAR_MAX to RANDMAX until RANDMAX is no less than
         GENMAX.  This may lose up to CHAR_BIT bits of information
         if shift_right (RANDINT_MAX) < GENMAX, but it is not
         worth the programming hassle of saving these bits since
         GENMAX is rarely that large in practice.  */
      ...
}

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

/* Consume random data from *S to generate a random buffer BUF of size
   SIZE.  */

void
randread (struct randread_source *s, void *buf, size_t size)
{
  if (s->source)
    readsource (s, buf, size);
  else
    readisaac (&s->buf.isaac, buf, size);
}

то есть на низком уровне нет прямой зависимости между shufвходным значением и данными, считанными из источника случайности (кроме вычисления требуемой емкости байтового буфера).

дирижабль
источник
6
Разве это не дает входные данные в качестве аргумента вашему генератору случайных чисел?
Мартин Эндер
Даже если это не верно, отправьте другой ответ от bash!
@MartinEnder хорошо, а не напрямую, он просто использует входные данные для определения верхнего предела для сгенерированного целочисленного диапазона и jot will arrange for all the values in the range to appear in the output with an equal probability(это, вероятно, граница, но все же).
дирижабль
2
Если я покопаюсь достаточно глубоко в каком-либо генераторе случайных чисел, я уверен, что найду вызов в низкоуровневый ГСЧ, который напрямую не использует исходный аргумент. Задача состоит в том, чтобы получить равномерный дистрибутив произвольного размера из дистрибутива с фиксированным размером, который вы до сих пор не делаете.
Мартин Эндер
1

SmileBASIC, 38 байт

INPUT N@L
R=RND(1<<30)ON N<=R GOTO@L?R

Генерирует случайные числа до тех пор, пока не получит то, которое меньше входного.

12Me21
источник
1

Рубин, 23 15 23 32 29 байт

->n{1while n<q=rand(2**30);q}

Как это работает:

  • 1while [...]; выполняет оператор хотя бы один раз: 1 прежде чем whileдействует как nop
  • Получить случайное число в диапазоне 0..2 ^ 30-1 ( ниже 2 ^ 30 , как указано)
  • Повторите, если число больше, чем входной параметр (может потребоваться некоторое время, когда n мало)
гигабайт
источник
1

Ом, 26 байт

IΩ
D31º#╬D0[>?D-+∞;,

Объяснение:

IΩ                 ■Main wire
IΩ                 ■Call wire below

D31º#╬D0[>?D-+∞;,  ■"Real main" wire
D                  ■Duplicate input
 31º#╬D            ■Push random_int in [0..2^31] twice
       0[          ■Push input again
         >?    ;   ■If(random_int > input){
           D-+     ■  remove the random_int
              ∞    ■  recursion
               ;   ■}
                ,  ■Print random_int
Роман Греф
источник
Есть ли переводчик для этого языка? А как насчет кодовой страницы?
ATaco
@ATaco: переводчик , кодовая страница: CP-437
Emigna
1

Идти, 63 61 байт

import."math/rand"
var n=0;func R(){q:=n;for;q<n+1;n=Int(){}}

Используйте это так:

func main() {
    n = 5000
    R()
    print(n)
}

Проверьте это в прямом эфире на игровой площадке

Кристоффер Салл-Сторгард
источник
В соответствии с нашими значениями по умолчанию, взятие ввода из предопределенных переменных и запись вывода в предопределенные переменные не допускаются. Вы могли бы использовать указатели на глобальные переменные, хотя
Деннис
1

Голанг, 84 78 71 байт

import."math/rand"
func R(n int)int{q:=n+1;for;q>=n;q=Int(){};return q}

Простая отбраковка выборки.

Примечание: так как математическое / рандовое начальное число является константой 1, вызывающий должен задавать, если не требуется постоянный результат.

Тест: https://play.golang.org/p/FBB4LKXo1r Больше не тестируется практически на 64-битной системе, поскольку он возвращает 64-битную случайность и использует тестирование на отклонение.

package main

import "fmt"
import "time"

/* solution here *//* end solution */

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
Riking
источник
1
если вы используете, import."math/rand"то Int31доступно в глобальном пространстве имен, и вы можете сохранить 4 байта, также intгарантированно не менее 32 бит, что сэкономит вам еще 6 байтов
Kristoffer Sall-Storgaard
Используйте :=синтаксис для еще 3 байтов
Кристоффер Салл-Сторгард,
Использование int вместо int32 не сохраняет никаких байтов, так как нам нужно привести результат Int31 () - 3 * int + () = 11 байтов против 2 * int32 = 10 байтов.
Riking
1
Не нужно Int()import
Kristoffer Sall-Storgaard