Что за странная функция

45

Ваша задача здесь будет заключаться в том, чтобы реализовать функцию 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 ...

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

Определение вероятности

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

Допустим, у нас есть функция f . Вероятность того, что число будет нечетным, будет определяться как предел отношения нечетных членов набора к размеру набора f{1n} когда n стремится к бесконечности.

limn|{x:x{1n},odd(f(x))}|n

Например, вышеупомянутая функция будет иметь вероятность быть нечетной 2/3 .


Это поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.


Дополнительные проблемы

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

  • Запишите перестановку с нечетной вероятностью . (это возможно)1

  • Напишите перестановку, которая имеет больше нечетных чисел, чем четные числа в для любого но имеет нечетную вероятность .f{1n}n1/2

  • Напишите перестановку, у которой нет определенной вероятности (то есть нет предела).


1: здесь функция будет означать программу или функцию. Это просто кусок кода, который принимает ввод и производит вывод.

Мастер пшеницы
источник

Ответы:

22

Желе , 7 байт

Æf^<¥4P

Меняет местами 2 с и 3 с в исходной факторизации входа. Вероятность шансов составляет 2/3 .

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

Как это устроено

Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.
Деннис
источник
Этот ответ довольно умный. Я верю, что понимаю, почему это работает, но вы можете включить доказательство того, что это работает, потому что сначала я нашел это не интуитивным.
Пшеничный волшебник
6
Доказательство того, что это перестановка: функция обратная. Подтверждение соотношения: вероятность того, что выходные данные являются нечетными, - это вероятность того, что в оригинале не было факторов 3, а именно, когда он не делится на три. Этот шанс 2/3.
Томсминг
15

Шелуха , 11 10 байт

-1 байт благодаря Лео и немного другой функции

Это имеет странную вероятность 1

!uΣz:NCNİ1

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

Индексирует последовательность:

[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

объяснение

!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers
H.PWiz
источник
1
Не могли бы вы объяснить функцию?
Пшеничный волшебник
1 байт меньше , с помощью Nub: tio.run/##yygtzv6vkFuce3jboeX6PsqqRrmPmhof7lhcdGjbf8XSc4urrPyc/...
Лео
8

Haskell, 35 34 32 байта

f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

Реализует пример последовательности [1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...].

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

Для справки: старая версия, 34 байта (-1 байт благодаря @xnor):

(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

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

Ними
источник
Спасите парен:(!!)$do ...
xnor
8

Шелуха , 8 байт

!uΣzeİ1N

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

Это реализует пример sequence ( 1,3,2,5,7,4...).

объяснение

!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input
Лео
источник
7

Все делают вызов 1, так что давайте сделаем два других.

Perl 6 , 26 байт - Задача 2

{($_==1)+$_-(-1)**($_%%2)}

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

Просто 1 3 2 5 4 7 6...в четном числе терминов всегда есть на 2 больше нечетных числа, чем четных. В нечетном числе еще 1. Однако это имеет явно предел (n+2)/(2n+2) -> ½.


Perl 6 , 70 байт - Задача 3

{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

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

По общему признанию, это ужасно игра в гольф. Он индексирует последовательность, содержащую 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 байт - основной вызов.

{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

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

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

Это пример последовательности.

Ramillies
источник
2
Это дополнительные проблемы. Чтобы это был правильный ответ, вы должны предоставить решение основной проблемы. Решение проблемы 1 также является решением основной проблемы, но решение проблем 2 или 3 - нет.
Питер Тейлор,
1
Что ж, для меня интересны дополнительные проблемы в этом вопросе. Основной проблемой не является. Но я все равно добавил какое-то решение.
Ramillies
Я попросил доказательства того, что ваш ответ на задание 3 не имеет ограничений в этом вопросе Math.SE
Кевин - восстановите Монику
@Kevin, спасибо, что спросил. Я думаю, что я мог запутать вас. Я был совершенно уверен, что все в порядке. Единственное, что я часто доказываю вещи довольно строго для себя, просто для душевного спокойствия (потому что ваши ноги могут довольно легко скользить, особенно при работе с такими бесконечными объектами) - и я не делал этого здесь. Это все, что я хотел сказать.
Ramillies
1
@Kevin - так что, в конце концов, я преодолел свою лень (героический поступок!) И сделал доказательство. Я отправил это как ответ на Ваш вопрос Math.SE. Надеюсь, все в порядке (делать такую ​​работу ночью не очень хорошая идея :—)). Оказалось, что это не так ужасно, как я изначально думал.
Ramillies
5

Brain-Flak , 120 байт

(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

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

Выполняет следующую функцию:

функция

Эта функция генерирует последовательность

2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

Функция имеет нечетную вероятность 1

0 '
источник
4

R, 82 байта (дополнительный вызов 1)

f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

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

Если вход является идеальным квадратом, дает четное число. В противном случае дает нечетное число. Совершенные квадраты имеют естественную плотность 0, что означает, что эта последовательность дает нечетные числа с вероятностью 1.

KSmarts
источник
Не могли бы вы добавить ссылку TIO, пожалуйста?
H.PWiz
1
58 байт
Джузеппе
56 байтов
Джузеппе
53 байта
Джузеппе
3

C (gcc) , 29 байт

f(n){return n&3?n+n/2|1:n/2;}

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

Каждый четвертый номер чётный:

1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

Дополнительный вызов 1, 52 байта

f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

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

Возвращает 2 * (x + 1), если n равно 2 x и последовательные нечетные числа в противном случае:

    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10      
nwellnhof
источник
3

Brain-Flak , 140 138 136 байт

({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

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

объяснение

Это выполняет функцию, аналогичную предложенной в вопросе.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

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

(({}(({}({}))[({}[{}])]))[({}[{}])])

Мы установили два стека, один со значениями аккумулятора (два нечетных, один четный) и один с числами 4 4 2. На каждой итерации мы бросаем оба стека и добавляем верх левого стека к вершине правого стека.

(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

Это будет увеличивать каждое нечетное число на 4, а одно четное число - на 2. Когда мы перебираем цикл, мы получаем комбинацию из 2 нечетного 1 четного числа с каждым положительным целым числом, попадающим в цель. Таким образом , мы просто цикл nраза nбыть вход. Это имеет асимптотическую вероятность 2/3 .

Мастер пшеницы
источник
2

Желе , 10 байт

ÆE;0ṭ2/FÆẸ

Вероятность шансов составляет 2/3 .

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

Как это устроено

ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.
Деннис
источник
1

Пакетный, 36 байт

@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

Реализует последовательность, приведенную в вопросе.

Нил
источник
1

JavaScript, 23 байта

n=>n/2+n/2%2+(n%4&&n-1)

Выход: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...

  • Для всех n = 4k:
    • f (n) = n / 2 = 2k
  • Для всех n = 4k + b
    • f (n) = n / 2 + b / 2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

Задача 2:

n=>n^(n>1)

Выход: 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 байт короче.
nwellnhof
1

CJam (21 байт)

{2b_(&!\_,2*\1$~+2b?}

Демоверсия онлайн, показывающая первые 32 выхода. Это анонимный блок (функция).

Это также решение задачи 1: числа, отображаемые на четные числа, являются степенями 2, поэтому плотность четных чисел в первых n выходных данных равна lg (n) / n, которая стремится к нулю.

рассечение

{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}
Питер Тейлор
источник
1

Brain-Flueue , 88 байт

({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

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

объяснение

Это реализует ту же функцию, что и мой последний ответ, но использует модель FIFO Brain-Flueue, чтобы срезать некоторые углы. Вот первые пару терминов, которые он генерирует.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Первая часть кода - это просто установка, мы помещаем 0,-1,-3первый стек и 2,4,4второй стек. Эта 2,4,4воля будет использоваться для циклического перебора четных и нечетных чисел, как я это делал в своем ответе «Мозговые флаки».

Затем мы выполняем цикл n раз, каждый раз добавляя вершину левого стека в правый стек. Поскольку Brain-Flueue использует очереди, а не стеки, значения естественным образом меняются, когда мы прикасаемся к ним, предотвращая необходимость в дополнительном коде.

Мастер пшеницы
источник
В чем разница между Flueue и Flak?
FantaC
@tfbninja Flueue использует очередь вместо стека.
Пшеничный Волшебник
но ... вы используете интерпретатор bflk ... как вы
измените
@tfbninja -lflueueАргумент.
Пшеничный волшебник
0

Python 2 , 46 104 55 байт

lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

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

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

Вероятность нахождения нечетного положительного целого числа теперь сходится к 1.

Джонатан Фрех
источник
Это должно вернуть число, а не набор / список, насколько я понял
г-н Xcoder
Кроме того, это не правильная перестановка, поскольку она содержит 0.
г-н Xcoder
@ Mr.Xcoder Спасибо, что заметили.
Джонатан Фрех
0

Pyth , 9 байт

*Fmxd<d4P

Попробуй это здесь! или проверить больше за один раз!

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

Km*Fmxk<k4PdS10000clf%T2KlK

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

Выше дает примерно 0,667 . Истинная вероятность нечетных случаев составляет 2/3 . Этот подход является эквивалентной реализацией ответа Денниса .


объяснение

*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.
Мистер Xcoder
источник
0

Java 8, 20 байт

n->n%4>0?n+n/2|1:n/2

Порт @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.

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

Кевин Круйссен
источник
0

Луа, 67 53 байта

Объяснение придет, когда я закончу играть в гольф :)

Эта программа принимает целое число через аргументы командной строки в качестве входных данных и печатает n-й элемент последовательности примеров в STDOUT

n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

Пояснения

n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

Четные числа этой последовательности являются nчетным и nкратным 3, поэтому n%3*2для их генерации достаточно формулы .

Для нечетных чисел это немного сложнее. Исходя из того, что мы можем найти их в зависимости от текущей n, мы имеем следующую таблицу:

n       |  1   2   4   5   7   8   10   11  
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

Давайте назовем значение target-n i, мы видим, что каждый раз n%3==2, iувеличивается. Там идет наша формула:

n+math.floor(n/3)+n%3-1

Нечетные числа основаны nна которых мы добавляем i.

Значение iувеличивается с той же скоростью, что и евклидово деление на 3, со смещением. math.floor(n/3)дает нам скорость приращения и n%3-1дает нам смещение, делая это n%3==2вместо n%3==0.

Katenkyo
источник
Один байт можно легко сохранить, удалив ненужный пробел ( ...and (n/...).
Джонатан Фрех
@JonathanFrech смог сохранить 2 на этом месте, полностью удалив скобки, так and n/3*2orже хорошо работает
Katenkyo