Dado un número positivo n , genera todas las particiones multiplicativas distintas de n en cualquier formato conveniente.
Una partición multiplicativa de n es un conjunto de enteros, todos mayores que uno, de modo que su producto es n . Por ejemplo, 20 tiene las siguientes particiones multiplicativas distintas:
2 * 2 * 5
2 * 10
4 * 5
20
El orden no importa, también lo 2 * 2 * 5
es la misma partición que 2 * 5 * 2
.
Ejemplos:
1 -> {}
2 -> {2}
4 -> {2, 2}, {4}
20 -> {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -> {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}
Respuestas:
Brachylog , 16 bytes
Esta es una función (no un programa completo) que toma un número positivo como entrada y genera todas sus particiones multiplicativas. (También evité usar las soluciones integradas de factorización principal en esta solución, principalmente porque no estaba seguro de que me ayudaran; en algún momento podría probar una solución más pesada también).
Pruébalo en línea! (Se ha agregado un código adicional alrededor de la función aquí para convertirlo en un programa completo; si proporciona la función que se muestra arriba a TIO directamente, ejecutará la función pero no imprimirá su salida en ningún lado, lo cual es inútil como demostración .)
Este programa realmente me decepciona, porque gran parte está solucionando errores en el intérprete de Brachylog y deficiencias en su especificación, en lugar de resolver el problema; pero el intérprete es lo que es. (Incluso con un programa como este, el intérprete usa mucha más memoria de la que debería lógicamente, y se bloquea debido al agotamiento de la memoria, pero afortunadamente en pequeños problemas se las arregla para producir la salida deseada primero.) En una hipotética "versión perfecta de Brachylog" simplemente podría escribir
~*.o.:{>1}a,
, que sería 4 bytes más corto, pero necesitaba agregar restricciones adicionales para ayudar un poco al intérprete. (Realmente no me gusta mucho Brachylog, y preferiría apegarme a Prolog, pero necesitaba sugerencias similares para que el programa funcionara y son mucho más largos de escribir. Así que Brachylog lo es).Explicación:
Como de costumbre, un programa Brachylog es un conjunto de restricciones; por defecto, la primera restricción restringe la entrada contra un desconocido (que llamaré A ), la segunda restricción restringe A contra un segundo B desconocido , y así sucesivamente hasta llegar a la salida. Algunos caracteres, como
{}
, pueden cambiar este flujo general, por lo que utilizo un conjunto diferente de letras (por ejemplo, X / Y ) para representar incógnitas en predicados anidados.Todavía no está claro cómo funciona el programa, así que intentemos simplificar un poco las restricciones. C , D , G , H e I son todos iguales (e iguales a la salida). E y F también son iguales (e iguales a la entrada). Entonces nuestras limitaciones se reducen a esto:
:{1<}a
necesita que su argumento izquierdo tenga una longitud restringida, o el intérprete entra en un bucle infinito).Por cierto, no especifiqué explícitamente que todos los elementos de la salida son enteros, algo que podría parecer necesario; sin embargo, el solucionador de restricciones de Brachylog no puede manejar no enteros, por lo que convenientemente producirá solo las soluciones que involucran enteros.
Claramente, "la longitud de la salida es menor que la entrada" será verdadera siempre que la salida sea una partición multiplicativa de la entrada (porque 2 x > x para todas las x no negativas , es decir, 2 x positivas ). Entonces podemos ignorar esa restricción; solo está ahí para darle al intérprete de Brachylog una estrategia de trabajo para evaluar el programa. Las otras restricciones (que la salida está ordenada, que su producto es la entrada y que todos sus elementos son mayores que 1) son la definición de una partición multiplicativa y, por lo tanto, esta función es básicamente una implementación directa de la pregunta.
fuente
Brachylog 1, 14 bytes
Pruébalo en línea!
Brachylog 2,
1110 bytes, desafío de fechas posteriores al idiomaPruébalo en línea!
Maltysen respondió esta pregunta en 17 bytes de Pyth, así que se me ocurrió una solución Brachylog de 16 bytes que funcionó traduciendo la especificación de la pregunta a Brachylog. Mientras hacía eso, Dennis escribió una solución Jelly de 15 bytes. Así que tuve que bajar a 14 bytes. Esta es una función que toma la entrada como argumento y devuelve una lista de todas las particiones (en lugar de un generador, como con mi otra solución).
Algún tiempo después de escribir esta respuesta, Dennis y yo logramos cooperar para que la solución Jelly se redujera a 11 bytes. Resulta que hay una nueva versión de Brachylog, con una sintaxis terser; es posterior al desafío, por lo que en realidad no cuenta, pero podría manejar el total de 11 bytes demasiado pronto tan pronto como se lanzó; Las revisiones posteriores del lenguaje (inspiradas en otros desafíos) pueden llegar hasta 10, como se ve aquí. Los dos programas son idénticos, y la única diferencia es la sintaxis.
A diferencia de mi otra solución, que no hizo mucho uso de "primitivas de golf", sino que planteó el problema directamente, esta ignora casi todo el poder de las restricciones de Brachylog y, en su lugar, hace su mejor impresión Jelly, escribiendo una cadena de restricciones para las cuales el argumento de la izquierda ya es conocido (y, por lo tanto, las restricciones simplemente actúan como mónadas en lugar de restricciones completas). Por lo tanto, utiliza el mismo algoritmo que la solución Pyth de @ Maltysen, que es probablemente la forma más fácil de resolver esto usando primitivas de golf típicas. (Curiosamente, la solución de "solo exponga el problema" en mi otra respuesta sería más corta si no fuera por errores / deficiencias en el intérprete Brachylog, a pesar de su falta de uso de primitivas de golf. Algún día necesito escribir un "Brachylog mejorado" para obtener una buena solución para este tipo de problema; A medida que los idiomas de golf van, Brachylog es realmente detallado.)
El programa consta de un generador y una envoltura a su alrededor. Primero, aquí hay una explicación del generador:
Esto casi resuelve el problema, pero terminamos generando muchas de las particiones muchas veces cada una. Por lo tanto, necesitamos un contenedor para deduplicar las soluciones:
fuente
Mathematica, 61 bytes
Define un operador unario (recursivo)
±
que devuelve la lista de particiones.fuente
Pyth - 17 bytes
Toma todas las permutaciones de la factorización prima, luego divide cada una de ellas y luego produce todas las particiones, luego solo retiene particiones distintas.
Test Suite .
fuente
Python 2, 70 bytes
Emite una lista de listas ordenadas. Por ejemplo
f(20)
es[[2, 2, 5], [2, 10], [4, 5], [20]]
.fuente
O(n)
y comparación con el competidor de Python 2 podría ser másO(n^4)
elegante, mientras que f (998) podría soplar memoria o el hardware podría morir dentro de la ejecución tiempo de est. 80 días con el otro algoritmo, este aquí converge después de aprox. 7 milisegundos en mi máquina para obtener el resultado[[2, 499], [998]]
. En mi opinión, el problema podría ser más que paraN > 998
lasRecursionError: maximum recursion depth exceeded in comparison
paradas del código anterior de Python 3 ... feliz golf :-)O(n^4)
es suficiente para mi envío Python2: D Considerando el caso de prueba 998, mi código se ejecutará 9 veces y calculará la(n+r-1)! / r! / (n-1)!
cantidad de tuplas cada vez, donder
crece linealmente desde 2, y n lo es9 - 2
. Pero bueno, al menos no tienes que ajustar el límite de recursión ...Jalea ,
141311 bytesPruébalo en línea!
Estaba bastante seguro de que la solución Jelly de @ Dennis podría mejorarse. Desafortunadamente, no logré batir el récord de Brachylog, pero logré empatarlo. Actualización : Con la ayuda de @Dennis, ahora ha mejorado; Supongo que Jelly recupera la corona.
Este programa es increíblemente ineficiente, tiene un rendimiento de O (2 n 2 ) (por lo que el caso de prueba anterior lo muestra para la entrada 4). Se completa rápidamente en 4, muy lentamente en 5, y puede no ser prácticamente posible correr para números más grandes.
Curiosamente, el Brachylog se mejoró al pasar de una solución que describía el problema (en la que Brachylog es bueno) a una solución que utilizaba un algoritmo basado en la factorización de la entrada (en la que Jelly es bueno); Mientras tanto, la solución Jelly se mejoró alejándose de sus puntos fuertes y volviendo a una solución que solo describe el problema.
Explicación:
Debido a que la salida de
Ḋx
está ordenada, cada subsecuencia también debe ordenarse y, por lo tanto, no tenemos que ordenarlas individualmente. Entonces, "la misma salida en diferentes órdenes es una parte duplicada" del problema, y los "todos los valores en la salida son> 1" parte del problema, resueltos por la generación. Aparte de eso, lo que básicamente estamos haciendo aquí es "encontrar todas las listas para las cualesP=³
", lo que hacemos (de una manera increíblemente ineficiente) al generar todas las listas en cuestión y luego filtrar las incorrectas.(Claramente, alguien necesita inventar un híbrido de Jelly y Brachylog, más un solucionador de restricciones realmente bueno , para que podamos escribir algo
{P=³}~
similar a un código de deduplicación y resolver el programa en una longitud mucho más corta. Eso podría ser aunque a cierta distancia).fuente
2r
Puede convertirseḊ
yP=³$$
puede convertirseP=¥
.P=¥
no funciona cuando lo intento en el intérprete, aunque no estoy completamente seguro de por qué (lógicamente, debería funcionar, y fue una de las cosas que intenté mientras escribía la publicación; solo lo intenté nuevamente para asegurarme de que, definitivamente no hace lo que esperaba).Ḋ
lo hace, sin embargo, así que supongo que está nuestro ahorro de un byte :-)µ
con¹
, yaµ
que el rango repetido es el nuevo argumento izquierdo.³
lugar de¹
solo la variedad.)JavaScript (ES6),
7467 bytesResuelve directamente el problema de forma recursiva: para cada número entero m de 2 a n , tomamos cada una de las particiones de n / m con un elemento mínimo de m (para evitar particiones duplicadas) y agregamos m . (Para cualquier m que no divida n , esto da la matriz vacía, ya que ninguna disposición de enteros se multiplica a un decimal.) Definimos un caso base de la matriz vacía para 1 para evitar una recursión infinita.
fuente
Python2,
198191172180 bytesUn programa completo Esto podría mejorarse mucho, por lo que las sugerencias son muy bienvenidas.
Salidas del rango 1 a 31 (inclusive):
fuente
4 -> {2, 2}, {4}
en cuestión, no veo esa salida en su registro.int(math.log(n,2))
, lo que causó eso. +2 bytes y funcionará. ¡Gracias!math
pero está utilizandomath.log
.len(bin(n))-2
es más corto queint(math.log(n,2))
.Jalea , 15 bytes
Pruébalo en línea!
fuente
Clojure, 91 bytes
Ejecuciones de ejemplo:
El valor en sí mismo se devuelve como un número único (no a
list
), otros salen como listas. Aln
final se puede reemplazar por[n]
hacer una secuencia también, o(list n)
para hacer una lista.fuente
Wolfram Language (Mathematica) ,
585652 bytesPruébalo en línea!
Adaptado de mi solución de Mathematica a Divisores Divisivos Divisores . Devuelve una
Sequence
de particiones.fuente
J, 35 bytes
Basado en la solución a un desafío de factorización de tiempo limitado.
Esta versión es mucho más ineficiente y se ejecuta en tiempo factorial en función del número de factores primos. Crea particiones generando números factoradic.
Pruébalo en línea! (¡No intentes valores grandes en línea!)
Explicación
fuente
D, 95 bytes
Solo una solución recursiva. En
g(n,r)
,r
es la partición hasta ahora, yn
es el valor que aún queda por dividir en factores. Para obtener cada partición desordenada solo una vez, clasificamos los factores enr
un orden no creciente. El último elemento der
comienza2
como el mínimo factor posible y se sobrescriben
en cada copia justo antes de cada operación de salida.por
n = 60
, la salida es la siguiente:Pruébalo en línea!
fuente
void g(T)(T n,T[]r){for(T i=r[0];i*i<=n;i++)n%i0:r;r.back=n;r.writeln;}g(n,[2])
std.stdio
ystd.range
, la entrada no1
debe imprimir nada, no[1]
.D, 109 bytes
Pruébalo en línea!
fuente