Su tarea aquí será implementar una función 1 que forme una permutación en los enteros positivos (una biyección de los enteros positivos en sí mismos). Esto significa que cada entero positivo debería aparecer exactamente una vez en la permutación. El problema es que su función debe tener una mayor probabilidad de generar un número impar que un número par.
Ahora esto puede parecer extraño o imposible. ¿Seguramente hay tantos números impares como pares? Y aunque esta intuición es correcta para conjuntos finitos, en realidad no es válida para conjuntos infinitos. Por ejemplo, tome la siguiente permutación:
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 ...
Si toma cualquier subsección de la secuencia con un tamaño mayor que , tendrá al menos tantos números impares como pares, por lo que parece que la probabilidad de que cualquier término aleatorio sea impar es mayor que la de ser par. También notará que cada número impar o par eventualmente aparecerá en la secuencia y solo puede aparecer una vez. Así, la secuencia es una verdadera permutación.
Definición de probabilidad
Para evitar confusiones o ambigüedades, voy a exponer claramente lo que se entiende por probabilidad en esta pregunta.
Digamos que tenemos una función . La probabilidad de que un número sea impar se definirá como el límite de la proporción de miembros impares del conjunto al tamaño del conjunto ya que tiende hacia el infinito.
Por ejemplo, la función mencionada tendría una probabilidad de ser impar de .
Este es el código de golf, por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.
Retos extra
Aquí hay algunas ideas divertidas para jugar y quizás intentar implementar. Estos son solo por diversión y no afectan la puntuación de ninguna manera. Algunas de estas ni siquiera son soluciones válidas para este desafío, y una respuesta que solo incluye soluciones para los desafíos 2 o 3 no es una respuesta válida y es probable que se elimine .
Escribe una permutación con una probabilidad impar de . (Esto es posible)
Escriba una permutación que tenga más números impares que números pares en para cualquier pero tiene una probabilidad impar de .
Escriba una permutación que no tenga una probabilidad definida (es decir, no hay límite).
1: Aquí la función significará programa o función. Es solo un fragmento de código que toma entrada y produce salida.
Casco ,
1110 bytes-1 byte gracias a Leo, y una función ligeramente diferente
Esto tiene una probabilidad extraña de
1
Pruébalo en línea!
Indiza la secuencia:
Explicación
fuente
Haskell,
353432 bytesImplementa la secuencia de ejemplo
[1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...]
.Pruébalo en línea!
Para referencia: versión anterior, 34 bytes (-1 byte gracias a @xnor):
Pruébalo en línea!
fuente
(!!)$do ...
Casco , 8 bytes
Pruébalo en línea!
Esto implementa la secuencia de ejemplo (
1,3,2,5,7,4...
).Explicación
fuente
Todos hacen el Desafío 1, así que hagamos los otros dos.
Perl 6 , 26 bytes - Desafío 2
Pruébalo en línea!
Es solo que
1 3 2 5 4 7 6...
en un número par de términos, siempre hay 2 números impares más que pares. En un número impar, 1 más. Sin embargo esto tiene un límite claro de(n+2)/(2n+2) -> ½
.Perl 6 , 70 bytes - Desafío 3
Pruébalo en línea!
Es cierto que esto es horriblemente golf. Indexa una secuencia que contiene 2⁰ números impares, luego 2¹ pares, luego 2² impares, luego 2³ pares, y así sucesivamente.
La probabilidad después de n tales "bloques", si n es impar, es (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). La suma en el numerador es igual a ⅓ (4 ½ (n + 1) - 1) = ⅓ (2 n + 1 - 1). Entonces, la probabilidad después de un número impar de bloques es ⅔ (en el límite).
Si agregamos un bloque más (y hacemos un recuento par de ellos n + 1), sin embargo, no agregamos ningún número impar (el numerador permanece igual) pero ahora hay (2 n + 1 - 1) números en total . Los paréntesis se cancelan y obtenemos la probabilidad de ⅓ (en el límite).
Aparentemente, se supone que esto tiene 2 puntos de clúster diferentes, ⅓ y ⅔, para asegurarse de que el límite no exista, pero esto realmente no lo prueba. Mi intento de hacer una prueba sólida y rigurosa se puede encontrar en esta respuesta de Math.SE: https://math.stackexchange.com/a/2416990/174637 . Errores de golpe son bienvenidos.
Perl 6 , 39 bytes: el desafío principal.
Pruébalo en línea!
Aunque publiqué esta respuesta debido a los desafíos 2 y 3 que ofrecían un pequeño y agradable rompecabezas matemático, existe un requisito estricto para que todas las respuestas contengan una solución al desafío central. Aquí está entonces.
Esta es la secuencia de ejemplo.
fuente
Brain-Flak , 120 bytes
Pruébalo en línea!
Realiza la siguiente función:
Esta función genera la secuencia.
La función tiene una probabilidad impar de
1
fuente
R, 82 bytes (desafío adicional 1)
Pruébalo en línea!
Si la entrada es un cuadrado perfecto, da un número par. De lo contrario, da un número impar. Los cuadrados perfectos tienen densidad natural 0, lo que significa que esta secuencia da números impares con probabilidad 1.
fuente
C (gcc) , 29 bytes
Pruébalo en línea!
Cada cuarto número es par:
Desafío adicional 1, 52 bytes
Pruébalo en línea!
Devuelve 2 * (x + 1) si n es igual a 2 x y números impares consecutivos de lo contrario:
fuente
Cerebro-Flak ,
140138136 bytesPruébalo en línea!
Explicación
Esto realiza una función similar a la sugerida en la pregunta.
Funciona principalmente en base a un fragmento que hice para rodar la pila para pilas de tamaño 3.
Configuramos dos pilas, una con valores de acumulador (dos impares, par) y otra con los números
4 4 2
. En cada iteración tiramos ambas pilas y agregamos la parte superior de la pila izquierda a la parte superior de la pila derecha.Esto incrementará cada número impar en 4 y el número par en 2. A medida que avanzamos, obtenemos un patrón de 2 pares 1 impares, con cada número entero positivo golpeado. Por lo tanto, simplemente repetimos los
n
tiempos conn
ser la entrada. Esto tiene una probabilidad asintótica de 2/3 .fuente
Jalea , 10 bytes
La probabilidad de probabilidades es 2/3 .
Pruébalo en línea!
Cómo funciona
fuente
C, 80 bytes
Implementación del ejemplo de permutación de la pregunta.
Pruébalo en línea!
fuente
Lote, 36 bytes
Implementa la secuencia dada en la pregunta.
fuente
JavaScript, 23 bytes
Salida: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...
Desafío 2:
Salida: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14
fuente
n=>n%4?1.5*n|1:n/2
es 5 bytes más corto.CJam (21 bytes)
Demostración en línea que muestra las primeras 32 salidas. Este es un bloque anónimo (función).
Esta también es una solución para el desafío 1: los números asignados a números pares son las potencias de 2, por lo que la densidad de los números pares en las primeras n salidas es lg (n) / n, que tiende a cero.
Disección
fuente
Perl 40 bytes
fuente
Flujo cerebral , 88 bytes
Pruébalo en línea!
Explicación
Esto implementa la misma función que mi última respuesta, pero utiliza el modelo FIFO de Brain-Flueue para cortar algunas esquinas. Aquí están los primeros dos términos que genera.
La primera parte del código es solo un poco de configuración, colocamos
0,-1,-3
en la primera pila y2,4,4
en la segunda pila. Se2,4,4
utilizará para recorrer los números pares e impares tal como lo hice en mi respuesta Brain-Flak.Luego hacemos un bucle n veces, cada vez que agregamos la parte superior de la pila izquierda a la pila derecha. Dado que Brain-Flueue usa colas en lugar de pilas, los valores se mueven naturalmente a medida que los tocamos, evitando la necesidad de código adicional.
fuente
-lflueue
argumento.Python 2 ,
4610455 bytesPruébalo en línea!
Leyó mal la pregunta, ahora implementó correctamente una función que puede usarse para generar una secuencia en lugar de una que genera una secuencia. También excluido
0
del conjunto de salidas posibles.La probabilidad de encontrar un número entero impar impar ahora converge
1
.fuente
0
.Jalea , 9 bytes
Pruébalo en línea!
Implementos
1, 3, 2, 5, 7, 4, 9, 11, 6, ...
(probabilidad 2/3).fuente
05AB1E , 11 bytes
Pruébalo en línea!
fuente
Pyth , 9 bytes
Pruébalo aquí! o prueba más de una vez!
Puede usar este código para verificar la proporción de números impares hasta cierto punto. Sustituya
10000
con su límite deseado (no lo establezca mucho más alto, porque tiene errores de memoria).Probar aquí .
Lo anterior da aproximadamente 0.667 . La verdadera probabilidad de ocurrencias extrañas es 2/3 . Este enfoque es una implementación equivalente de la respuesta de Dennis .
Explicación
fuente
Java 8, 20 bytes
La respuesta C del puerto de @nwellnhof .
Algunas cosas que probé terminaron siendo unos bytes más largos o ligeramente incorrectos.
Implementos:
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,...
con una probabilidad de
3/4
.Pruébalo aquí
fuente
Lua,
6753 bytesLa explicación viene cuando termine de jugar golf :)Este programa toma un número entero a través de argumentos de línea de comandos como entrada e imprime el enésimo elemento de la secuencia de ejemplo en STDOUT
Explicaciones
Los números pares de esta secuencia son el
n
número par y eln
múltiplo de 3, por lo tanto, la fórmulan%3*2
es suficiente para generarlos.Para números impares, es un poco más difícil. Basado en el hecho de que podemos encontrarlos dependiendo de la corriente
n
, tenemos la siguiente tabla:Llamemos al valor
target-n
i
, podemos ver que cada vezn%3==2
,i
se incrementa. Ahí va nuestra fórmula:Los números impares se basan
n
en los que agregamosi
.El valor de los
i
incrementos a la misma velocidad que la división euclidiana por 3, con un desplazamiento.math.floor(n/3)
nos da la tasa de incremento yn%3-1
nos da el desplazamiento, haciendo que ocurra enn%3==2
lugar den%3==0
.fuente
...and (n/...
).and n/3*2or
funciona igual de bien