Listar todas las particiones multiplicativas de n

28

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 * 5es 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}
orlp
fuente
Relacionado
millas del

Respuestas:

6

Brachylog , 16 bytes

>~l:{1<}a.*?,.=o

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.

>       A is smaller than the input
~l      B has length A
  1<    X is 1, Y is larger
:{1<}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I

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:

  • A es la longitud de B y de la salida, y es más pequeña que la entrada.
  • B consiste en todos los 1, y no es particularmente útil (es parte del programa simplemente porque en el intérprete Brachylog existente, :{1<}anecesita que su argumento izquierdo tenga una longitud restringida, o el intérprete entra en un bucle infinito).
  • La salida consiste completamente en números mayores que 1 (es decir, mayores que el elemento correspondiente de B ).
  • El producto de los elementos de la salida es igual a la entrada.
  • La salida no cambia al ordenarla (es decir, está ordenada).

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
6

Brachylog 1, 14 bytes

:{$pp~c:*ao}fd

Pruébalo en línea!

Brachylog 2, 11 10 bytes, desafío de fechas posteriores al idioma

{ḋp~c×ᵐo}ᵘ

Prué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:

$pp~c:*ao  ḋp~c×ᵐo
$p         ḋ        Prime factor decomposition of the input
  p         p       Generate all permutations
   ~c        ~c     Generate all inverse concatenations (i.e. partitions)
     :*a       ×ᵐ   Take the product of each list element in each partition
        o        o  Sort each partition

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:

:{…}fd
:{…}f     Convert generator to list
     d    Remove duplicate elements

{…}ᵘ      Convert generator to list of unique elements

fuente
¿Por qué no editas tu respuesta?
Downgoat
3
@Downgoat: las dos respuestas utilizan enfoques completamente diferentes; los algoritmos son diferentes, las características del lenguaje que se usan son en su mayoría independientes y similares. No tendría sentido reemplazar el anterior con el nuevo (y bien podría haber publicado el nuevo incluso si fuera más largo). Esta meta publicación sugiere que publicar respuestas separadas es preferible en este tipo de situación.
1
No sé si sabe esto, pero puede recuperar el resultado configurando el argumento en TIO para que sea una variable (es decir, una letra mayúscula). Por ejemplo .
Fatalize
5

Mathematica, 61 bytes

±1={{}}
±n_:=Union@@(Sort/@Append[n/#]/@±#&/@Most@Divisors@n)

Define un operador unario (recursivo) ±que devuelve la lista de particiones.

Martin Ender
fuente
¿Mathica no requiere el punto y coma al final?
Pavel
@Pavel no, el punto y coma solo suprime la salida en el cuaderno interactivo. Gracias por señalar esto, por cierto, accidentalmente dejé un punto y coma al final.
Martin Ender
4

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.

{mS-*Md1s./M.p+1P

Test Suite .

Maltysen
fuente
4

Python 2, 70 bytes

f=lambda n,k=2,l=[]:n/k and(n%k<1)*f(n/k,k,l+[k])+f(n,k+1,l)or 1/n*[l]

Emite una lista de listas ordenadas. Por ejemplo f(20)es [[2, 2, 5], [2, 10], [4, 5], [20]].

xnor
fuente
Como el tipo entero incorporado de Python no tiene límites, el punto flotante no es una solución aceptable ya que las imprecisiones romperán la respuesta para entradas demasiado grandes.
orlp
@orlp Ok, de vuelta a Python 2 entonces.
xnor
TL; DR Creo que 998 no es una entrada demasiado grande ;-) IMO un código realmente genial, más como latencia O(n)y comparación con el competidor de Python 2 podría ser más O(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 para N > 998las RecursionError: maximum recursion depth exceeded in comparisonparadas del código anterior de Python 3 ... feliz golf :-)
Dilettant
@Dilettant No estoy seguro si 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, donde rcrece linealmente desde 2, y n lo es 9 - 2. Pero bueno, al menos no tienes que ajustar el límite de recursión ...
Yytsi
Advertencia de @TuukkaX: No analicé el código, simplemente lo hojeé y comparé el desarrollo de los tiempos de ejecución entre los dos candidatos para algunos N hasta 41, luego pensé que solo cometía el comentario ;-) las pilas y la recursión a menudo son fáciles, pero luego llamar para preguntas tipo ¿qué tan profundo en situaciones desagradables ... espero acuñé lo suficientemente difusa para la cantidad de investigación que entró.
Dilettant
3

Jalea , 14 13 11 bytes

Ḋx³ŒPQP=¥Ðf

Prué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:

Ḋx³ŒPQP=¥Ðf
Ḋ              List of integers from 2 to the input (apparently undocumented)
 x³            Make a number of copies of each that's equal to the input
   ŒP          Take all (possibly noncontiguous) subsequences of that list (!)
     Q         Remove duplicates
         Ðf    Filter, keeping elements where:
      P=         their product is equal to {the original input, by default}
        ¥      Parse preceding two links as a unit

Debido a que la salida de Ḋxestá 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 cuales P=³", 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
Por favor, alguien encuentre un personaje de ahorro aquí. Me encantaría una "guerra de bytes" en la que las entradas siguen acortándose un byte cada vez. Aquí se desperdician suficientes bytes en las partes estructurales del programa que parece que esto podría mejorarse.
1
Je, estaba a punto de publicar algo sorprendentemente similar. (Debería actualizarse más a menudo). 2rPuede convertirse y P=³$$puede convertirse P=¥.
Dennis
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 :-)
1
No le presté atención a otro detalle. Tendría que reemplazar también µcon ¹, ya µque el rango repetido es el nuevo argumento izquierdo.
Dennis
Oh por supuesto. Así que ahora tenemos 11, con muchos menos personajes, lo que me hace sentir mucho mejor. (Utilicé en ³lugar de ¹solo la variedad.)
2

JavaScript (ES6), 74 67 bytes

f=(n,m=2,a=[])=>n>1?m>n?[]:f(n,m+1,a).concat(f(n/m,m,[...a,m])):[a]

for (var i = 1; i < 31; i++) console.log(JSON.stringify(f(i)));

Resuelve 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.

ETHproducciones
fuente
1

Python2, 198 191 172 180 bytes

from itertools import*
n=input()
for i in range(2,len(bin(n))):
 for P in combinations_with_replacement(range(2,n),i):
  if reduce(lambda a,b:a*b,P)==n:print(P)
print[(n,),()][n<2]

Un programa completo Esto podría mejorarse mucho, por lo que las sugerencias son muy bienvenidas.

Salidas del rango 1 a 31 (inclusive):

(1,)
(2,)
(3,)
(2, 2), (4,)
(5,)
(2, 3), (6,)
(7,)
(2, 4), (2, 2, 2), (8,)
(3, 3), (9,)
(2, 5), (10,)
(11,)
(2, 6), (3, 4), (2, 2, 3), (12,)
(13,)
(2, 7), (14,)
(3, 5), (15,)
(2, 8), (4, 4), (2, 2, 4), (2, 2, 2, 2), (16,)
(17,)
(2, 9), (3, 6), (2, 3, 3), (18,)
(19,)
(2, 10), (4, 5), (2, 2, 5), (20,)
(3, 7), (21,)
(2, 11), (22,)
(23,)
(2, 12), (3, 8), (4, 6), (2, 2, 6), (2, 3, 4), (2, 2, 2, 3), (24,)
(5, 5), (25,)
(2, 13), (26,)
(3, 9), (3, 3, 3), (27,)
(2, 14), (4, 7), (2, 2, 7), (28,)
(29,)
(2, 15), (3, 10), (5, 6), (2, 3, 5), (30,)
(31,)
Yytsi
fuente
¿Esto incluso funciona? Hay un caso de prueba 4 -> {2, 2}, {4}en cuestión, no veo esa salida en su registro.
Borsunho
@Borsunho Cuando hice retroceder la versión anterior, olvidé agregar +1 int(math.log(n,2)), lo que causó eso. +2 bytes y funcionará. ¡Gracias!
Yytsi
No ha importado mathpero está utilizando math.log.
orlp
@orlp tengo ...? En la tercera linea.
Yytsi
@TuukkaX Disculpe, yo solo miré las líneas superiores para las importaciones, ya que casi siempre están ahí ... Dicho esto, len(bin(n))-2es más corto que int(math.log(n,2)).
orlp
1

Clojure, 91 bytes

(defn f[n](conj(set(for[i(range 2 n):when(=(mod n i)0)j(f(/ n i))](sort(flatten[i j]))))n))

Ejecuciones de ejemplo:

(map f [20 84])
(#{20 (2 2 5) (4 5) (2 10)} #{(7 12) (2 2 3 7) (2 3 14) (2 2 21) (2 6 7) (6 14) (3 4 7) (3 28) (4 21) (2 42) 84})

El valor en sí mismo se devuelve como un número único (no a list), otros salen como listas. Al nfinal se puede reemplazar por [n]hacer una secuencia también, o (list n)para hacer una lista.

NikoNyrh
fuente
0

J, 35 bytes

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:

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

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:  Input: integer n
                                 q:  Prime factorization
(                              )@    Operate on them
                              #        Length
                            !@         Factorial
                         i.@           Range [0, i)
                     #\                Range [1, i]
                       #:              Mixed based conversion - Creates factoradic values
     ]                                 Get factors
            (    )"$~                  For each factoradic value
               /.                        Partition the factors based on equal
                                         digits in the factoradic value
             */                          Get the product of each block
        /:~@                             Sort it
      <@                                 Box it
 [:~.                                  Deduplicate
millas
fuente
0

D, 95 bytes

void g(int n,int[]r){for(int i=r[0];i*i<=n;i++)(n%i)?0:g(n/i,i~r);r.back=n;r.writeln;}g(n,[2]);

Solo una solución recursiva. En g(n,r), res la partición hasta ahora, y nes el valor que aún queda por dividir en factores. Para obtener cada partición desordenada solo una vez, clasificamos los factores en run orden no creciente. El último elemento der comienza 2como el mínimo factor posible y se sobrescribe nen cada copia justo antes de cada operación de salida.

por n = 60 , la salida es la siguiente:

[3, 2, 2, 5]
[2, 2, 15]
[3, 2, 10]
[5, 2, 6]
[2, 30]
[4, 3, 5]
[3, 20]
[4, 15]
[5, 12]
[6, 10]
[60]

Pruébalo en línea!

Gassa
fuente
Usa las plantillas, Gassa, usa las plantillas: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])
Zacharý
De todos modos, esto ni siquiera es una respuesta válida, ya que necesita importar std.stdioy std.range, la entrada no 1debe imprimir nada, no [1].
Zacharý
0

D, 109 bytes

import std.stdio;void g(T)(T n,T[]r=[2]){if(n-1){for(T i=r[0];i*i<=n;i++)n%i?0:g(n/i,i~r);r[$-1]=n;r.write;}}

Pruébalo en línea!

Zacharý
fuente