Ваша задача здесь будет заключаться в том, чтобы реализовать функцию 1, которая формирует перестановку положительных целых чисел (биекция от положительных целых чисел на себя). Это означает, что каждое положительное целое число должно появляться ровно один раз в перестановке. Уловка в том, что ваша функция должна иметь большую вероятность вывести нечетное число, чем четное число.
Теперь это может показаться странным или невозможным. Конечно, нечетных чисел столько же, сколько четных? И хотя эта интуиция верна для конечных множеств, на самом деле она не справедлива для бесконечных множеств. Например, возьмите следующую перестановку:
1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...
Если вы возьмете какой-либо подраздел последовательности с размером больше вас будет по крайней мере столько же нечетных чисел, сколько и четных чисел, поэтому кажется, что вероятность того, что любой случайный член будет нечетным, больше, чем вероятность быть четным. Вы также заметите, что каждое нечетное или четное число в конечном итоге появится в последовательности и может появиться только один раз. Таким образом, последовательность является истинной перестановкой.
Определение вероятности
Чтобы избежать путаницы или двусмысленности, я собираюсь четко изложить, что подразумевается под вероятностью в этом вопросе.
Допустим, у нас есть функция . Вероятность того, что число будет нечетным, будет определяться как предел отношения нечетных членов набора к размеру набора когда стремится к бесконечности.
Например, вышеупомянутая функция будет иметь вероятность быть нечетной .
Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.
Дополнительные проблемы
Вот несколько забавных идей, с которыми можно поиграть и, возможно, попытаться реализовать. Это просто для удовольствия и никак не влияет на выигрыш. Некоторые из них даже не являются действительными решениями этой проблемы, и ответ, который включает в себя только решения для задач 2 или 3, не является действительным ответом и может быть удален .
Запишите перестановку с нечетной вероятностью . (это возможно)
Напишите перестановку, которая имеет больше нечетных чисел, чем четные числа в для любого но имеет нечетную вероятность .
Напишите перестановку, у которой нет определенной вероятности (то есть нет предела).
1: здесь функция будет означать программу или функцию. Это просто кусок кода, который принимает ввод и производит вывод.
Шелуха ,
1110 байт-1 байт благодаря Лео и немного другой функции
Это имеет странную вероятность
1
Попробуйте онлайн!
Индексирует последовательность:
объяснение
источник
Haskell,
353432 байтаРеализует пример последовательности
[1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...]
.Попробуйте онлайн!
Для справки: старая версия, 34 байта (-1 байт благодаря @xnor):
Попробуйте онлайн!
источник
(!!)$do ...
Шелуха , 8 байт
Попробуйте онлайн!
Это реализует пример sequence (
1,3,2,5,7,4...
).объяснение
источник
Все делают вызов 1, так что давайте сделаем два других.
Perl 6 , 26 байт - Задача 2
Попробуйте онлайн!
Просто
1 3 2 5 4 7 6...
в четном числе терминов всегда есть на 2 больше нечетных числа, чем четных. В нечетном числе еще 1. Однако это имеет явно предел(n+2)/(2n+2) -> ½
.Perl 6 , 70 байт - Задача 3
Попробуйте онлайн!
По общему признанию, это ужасно игра в гольф. Он индексирует последовательность, содержащую 2⁰ нечетных чисел, затем 2¹ четных, затем 2² нечетных, затем 2³ четных и так далее.
Вероятность после n таких «блоков», если n нечетно, равна (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). Сумма в числителе равна ⅓ (4 ½ (n + 1) - 1) = ⅓ (2 n + 1 - 1). Таким образом, вероятность после нечетного числа блоков равна ⅔ (в пределе).
Однако, если мы добавим еще один блок (и сделаем четное число из них n + 1), мы не добавим нечетных чисел (числитель останется прежним), но теперь общее количество (2 n + 1 - 1) чисел , Скобки отменяются, и мы получаем вероятность ⅓ (в пределе).
Предполагается, что это должно иметь две разные точки кластера, ⅓ и ⅔, чтобы убедиться, что предел не существует, но это на самом деле не доказывает это. Моя попытка сделать твердое, строгое доказательство может быть найдена в этом ответе Math.SE: https://math.stackexchange.com/a/2416990/174637 . Бить ошибки можно только приветствовать.
Perl 6 , 39 байт - основной вызов.
Попробуйте онлайн!
Хотя я и опубликовал этот ответ из-за проблем 2 и 3, в которых была предложена приятная маленькая математическая головоломка, для всех ответов существует жесткое требование содержать решение основной задачи. Вот тогда это.
Это пример последовательности.
источник
Brain-Flak , 120 байт
Попробуйте онлайн!
Выполняет следующую функцию:
Эта функция генерирует последовательность
Функция имеет нечетную вероятность
1
источник
R, 82 байта (дополнительный вызов 1)
Попробуйте онлайн!
Если вход является идеальным квадратом, дает четное число. В противном случае дает нечетное число. Совершенные квадраты имеют естественную плотность 0, что означает, что эта последовательность дает нечетные числа с вероятностью 1.
источник
C (gcc) , 29 байт
Попробуйте онлайн!
Каждый четвертый номер чётный:
Дополнительный вызов 1, 52 байта
Попробуйте онлайн!
Возвращает 2 * (x + 1), если n равно 2 x и последовательные нечетные числа в противном случае:
источник
Brain-Flak ,
140138136 байтПопробуйте онлайн!
объяснение
Это выполняет функцию, аналогичную предложенной в вопросе.
Он работает в основном на основе фрагмента, который я сделал, чтобы бросить стопку для стеков размера 3.
Мы установили два стека, один со значениями аккумулятора (два нечетных, один четный) и один с числами
4 4 2
. На каждой итерации мы бросаем оба стека и добавляем верх левого стека к вершине правого стека.Это будет увеличивать каждое нечетное число на 4, а одно четное число - на 2. Когда мы перебираем цикл, мы получаем комбинацию из 2 нечетного 1 четного числа с каждым положительным целым числом, попадающим в цель. Таким образом , мы просто цикл
n
разаn
быть вход. Это имеет асимптотическую вероятность 2/3 .источник
Желе , 10 байт
Вероятность шансов составляет 2/3 .
Попробуйте онлайн!
Как это устроено
источник
C, 80 байтов
Реализация примера перестановки из вопроса.
Попробуйте онлайн!
источник
Пакетный, 36 байт
Реализует последовательность, приведенную в вопросе.
источник
JavaScript, 23 байта
Выход: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...
Задача 2:
Выход: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14
источник
n=>n%4?1.5*n|1:n/2
на 5 байт короче.CJam (21 байт)
Демоверсия онлайн, показывающая первые 32 выхода. Это анонимный блок (функция).
Это также решение задачи 1: числа, отображаемые на четные числа, являются степенями 2, поэтому плотность четных чисел в первых n выходных данных равна lg (n) / n, которая стремится к нулю.
рассечение
источник
Perl 40 байт
источник
Brain-Flueue , 88 байт
Попробуйте онлайн!
объяснение
Это реализует ту же функцию, что и мой последний ответ, но использует модель FIFO Brain-Flueue, чтобы срезать некоторые углы. Вот первые пару терминов, которые он генерирует.
Первая часть кода - это просто установка, мы помещаем
0,-1,-3
первый стек и2,4,4
второй стек. Эта2,4,4
воля будет использоваться для циклического перебора четных и нечетных чисел, как я это делал в своем ответе «Мозговые флаки».Затем мы выполняем цикл n раз, каждый раз добавляя вершину левого стека в правый стек. Поскольку Brain-Flueue использует очереди, а не стеки, значения естественным образом меняются, когда мы прикасаемся к ним, предотвращая необходимость в дополнительном коде.
источник
-lflueue
Аргумент.Python 2 ,
4610455 байтПопробуйте онлайн!
Неправильно прочитанный вопрос, теперь правильно реализована функция, которая может использоваться для генерации последовательности вместо той, которая генерирует последовательность. Также исключен
0
из набора возможных выходов.Вероятность нахождения нечетного положительного целого числа теперь сходится к
1
.источник
0
.Желе , 9 байт
Попробуйте онлайн!
Реализует
1, 3, 2, 5, 7, 4, 9, 11, 6, ...
(вероятность 2/3).источник
05AB1E , 11 байт
Попробуйте онлайн!
источник
Pyth , 9 байт
Попробуй это здесь! или проверить больше за один раз!
Вы можете использовать этот код для проверки соотношения нечетных чисел до определенной точки. Замените
10000
желаемое ограничение (не устанавливайте его намного выше, потому что это ошибки памяти).Попробуй это здесь .
Выше дает примерно 0,667 . Истинная вероятность нечетных случаев составляет 2/3 . Этот подход является эквивалентной реализацией ответа Денниса .
объяснение
источник
Java 8, 20 байт
Порт @nwellnhof 's C ответа .
Некоторые вещи, которые я сам пробовал, оказались на несколько байт длиннее или немного неправильными.
Реализует:
1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
с вероятностью
3/4
.Попробуй это здесь.
источник
Луа,
6753 байтаОбъяснение придет, когда я закончу играть в гольф :)Эта программа принимает целое число через аргументы командной строки в качестве входных данных и печатает n-й элемент последовательности примеров в STDOUT
Пояснения
Четные числа этой последовательности являются
n
четным иn
кратным 3, поэтомуn%3*2
для их генерации достаточно формулы .Для нечетных чисел это немного сложнее. Исходя из того, что мы можем найти их в зависимости от текущей
n
, мы имеем следующую таблицу:Давайте назовем значение
target-n
i
, мы видим, что каждый разn%3==2
,i
увеличивается. Там идет наша формула:Нечетные числа основаны
n
на которых мы добавляемi
.Значение
i
увеличивается с той же скоростью, что и евклидово деление на 3, со смещением.math.floor(n/3)
дает нам скорость приращения иn%3-1
дает нам смещение, делая этоn%3==2
вместоn%3==0
.источник
...and (n/...
).and n/3*2or
же хорошо работает