Declaración del problema

Dado un conjunto de primos consecutivos únicos (que no incluyen necesariamente 2), genera los productos de todas las combinaciones de primeras potencias de estos primos, por ejemplo, sin repeticiones, y también 1. Por ejemplo, dado el conjunto {2, 3, 5, 7}, produce {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210} porque:

  1  =  1
  2  =  2
  3  =  3
  5  =  5
  6  =  2 x 3
  7  =  7
 10  =  2 x 5
 14  =  2 x 7
 15  =  3 x 5
 21  =  3 x 7
 30  =  2 x 3 x 5
 35  =  5 x 7
 42  =  2 x 3 x 7
 70  =  2 x 5 x 7
105  =  3 x 5 x 7
210  =  2 x 3 x 5 x 7

Tenga en cuenta que si la cardinalidad de su conjunto de entrada es k, esto le dará 2 ^ k miembros en su conjunto de salida.

Reglas / condiciones

1. Puedes usar cualquier idioma. Apunte al recuento de caracteres más pequeño del código fuente.
2. Su solución debe ser un programa completo o una función completa. La función puede ser anónima (si su idioma admite funciones anónimas).
3. Su solución debe poder admitir productos de al menos 2 ^ 31. No se preocupe por detectar o manejar el desbordamiento de enteros si se le pasan números cuyo producto es demasiado grande para representarlo. Sin embargo, indique los límites de sus cálculos.
4. Puede aceptar una lista o un conjunto y producir una lista o un conjunto. Puede suponer que la entrada está ordenada, pero no es necesario que produzca una salida ordenada.

Fondo

¿Cuándo o por qué es útil? Un lugar en el que es muy útil es generar una tabla de multiplicadores para competir en paralelo en un algoritmo de factorización de enteros conocido como Factorización de formas cuadradas. Allí, cada multiplicador impar que intente disminuye la probabilidad de que el algoritmo falle (para encontrar un factor) en aproximadamente un 50% en semiprimes duros. Entonces, con el conjunto de primos generadores {3, 5, 7, 11}, que produce un conjunto de 16 multiplicadores de prueba para correr en paralelo, el algoritmo falla aproximadamente 2 ^ –16 del tiempo en semiprimes duros. Agregar 13 a la lista de números primos produce un conjunto de 32 multiplicadores de prueba, lo que reduce la posibilidad de falla a aproximadamente 2 ^ –32, brindando una mejora drástica en el resultado sin gastos computacionales adicionales (porque incluso con el doble de multiplicadores compitiendo en paralelo, en promedio todavía encuentra la respuesta en el mismo número total de pasos).

Pure Bash, 32 bytes

eval echo \$[{1,${1// /\}*{1,}}]

Lee la lista de entrada (espacio único separado) pasado como una línea de comando arg.

Se utilizan tres expansiones de shell diferentes:

1. ${1// /\}*{1,}es un parámetro de expansión que reemplaza espacios 2 3 5 7con }*{1,para dar 2}*{1,3}*{1,5}*{1,7. \$[{1,y }]se agregan al inicio y al final respectivamente para dar \$[{1,2}*{1,3}*{1,5}*{1,7}]. La \$[barra invertida se escapó para evitar intentos de hacer una expansión aritmética en esta etapa.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}]Es una expansión de llaves . Debido a que la expansión de llaves normalmente ocurre antes de la expansión de parámetros , debemos usar evalpara forzar que la expansión de parámetros ocurra primero. El resultado de la expansión de la llave es $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7].
3. $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7]es una lista de expansiones aritméticas , que luego se evalúan para dar la lista de números que requerimos.

Salida:

$ ./comboprime.sh "2 3 5 7"
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210
$

CJam, 13 bytes

1aq~{1$f*+}/p

Lee una matriz (por ejemplo, [2 3 5 7]) de STDIN. Pruébalo en línea.

Una función anónima tendría el mismo número de bytes:

{1a\{1$f*+}/}

Ejecución de ejemplo

$ cjam <(echo '1aq~{1$f*+}/p') <<< '[]'
[1]
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[2 3 5 7]'
[1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210]

Cómo funciona

1a               " Push R := [1].              ";
  q~             " Read an array A from STDIN. ";
    {     }/     " For each a ∊ A:             ";
     1$f*+       "     R += { ra : r ∊ R }     ";
            p    " Print.                      ";

Haskell, 22

La solución es una función anónima:

map product.mapM(:[1])

ejemplo de uso:

*Main> map product.mapM(:[1]) $ [2,3,5]
[30,6,10,2,15,3,5,1]

explicación:
(:[1]) es una función que da un número xdevuelve la lista [x,1].
mapM(:[1])es una función que, dada una lista de números, asigna la función (:[1])sobre ellos y devuelve todas las formas posibles de elegir un elemento de cada lista. por ejemplo, mapM(:[1]) $ [3,4]primero asigna la función para obtener [[3,1] , [4,1]]. entonces las opciones posibles son [3,4](elegir el primer número de ambos) [3,1] [1,4]y [1,1]así regresa [[3,4],[3,1],[1,4],[1,1]].

luego map productasigna todas las opciones y devuelve sus productos, que son el resultado deseado.

Esta función es polimórfica en su tipo, lo que significa que puede operar en todo tipo de números. podría ingresar una lista de Inty el resultado sería una lista de, Intpero también podría aplicarse en una lista de tipoIntegery devolver una lista de Integer. esto significa que el comportamiento de desbordamiento no está especificado por esta función sino por el tipo de entrada (yay Haskell's typeive type system :))

Mathematica, 18 17 bytes

1##&@@@Subsets@#&

Esa es una función anónima. Llámalo como

1##&@@@Subsets@#&[{2,3,5,7}]

Actualización: C (función f), 92

Incluso como una función, esta sigue siendo la entrada más larga aquí. Es la primera vez que paso una matriz de longitud desconocida como argumento de función en C, y aparentemente no hay forma de que una función de C sepa la longitud de una matriz que se le pasó, ya que el argumento se pasa como un puntero ( independientemente de la sintaxis utilizada). Por lo tanto, se requiere un segundo argumento para indicar la longitud.

Mantuve la salida en stdout, porque configurar una matriz entera y devolverla seguramente sería más larga.

Gracias a Dennis por los consejos.

Vea la función f(92 caracteres excluyendo espacios en blanco innecesarios) en los programas de prueba a continuación.

Salida a través de printf

j;

f(int c,int*x){
  int p=1,i;
  for(i=c<<c;i--;p=i%c?p:!!printf("%d ",p))p*=(i/c>>i%c)&1?1:x[i%c];
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y);
}

Salida a través del puntero de matriz

j,q[512];

f(int c,int*x,int*p){
    for(int i=-1;++i-(c<<c);p[i/c]*=(i/c>>i%c)&1?1:x[i%c])i%c||(p[i/c]=1);
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y,q);
  for(j=1<<d;j--;)printf("%d ",q[j]);
}

C (programa), 108

excluyendo espacios en blanco innecesarios.

p=1,i;
main(int c,char**v){
  c-=1;
  for(i=c<<c;i--;i%c||(printf("%d ",p),p=1))(i/c>>i%c)&1||(p*=atoi(v[i%c+1]));
}

Entrada desde la línea de comandos, salida a stdout. C no va a ganar aquí, pero tal vez intente convertir a una función mañana.

Básicamente, iteramos a través de todas las 1<<ccombinaciones de primos, y cada bit i/cestá asociado con la presencia o ausencia de un primo particular en el producto. El "bucle interno" i%crecorre los números primos, multiplicándolos de acuerdo con el valor de i/c.Cuando i%calcanza 0, el producto sale, luego se establece en 1 para la siguiente iteración "externa".

curiosamente, printf("%d ",p,p=1)no funciona (siempre imprime un 1.) Esta no es la primera vez que veo un comportamiento extraño cuando se usa un valor en printfay se asigna más tarde en el mismo paréntesis. Es posible en este caso que la segunda coma no se trate como un separador de argumentos, sino más bien como un operador.

Uso

$ ./a 2 3 5 7
1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210

Haskell, 27 bytes

Esta es una implementación de Haskell de la respuesta CJam de @ sudo como una función anónima. No superará la increíble solución Haskell de @proud haskeller, pero la dejaré aquí de todos modos.

foldr((=<<)(++).map.(*))[1]

Explicación: foldr toma una función binaria, un valor y una lista. A continuación, se reemplaza cada célula contras en la lista por una aplicación de la función, y el final de la lista por el valor, como este: foldr f v [a,b,c] == f a (f b (f c v)). Nuestro valor es una lista de un elemento que contiene 1, y la función binaria es f = (=<<)(++).map.(*). Ahora, ftoma un número n, crea una función (n*)que se multiplica por n, hace de ella una función g = map(n*)que aplica esa función a todos los elementos de una lista y alimenta esa función (=<<)(++). Aquí, (++)está la función de concatenación, y (=<<)es un enlace monádico , que en este caso toma (++)y g, y da una función que toma una lista, se aplicag a una copia y concatena los dos.

En resumen: comience con [1], y para cada número nen la lista de entrada, tome una copia de la lista actual, multiplique todo por ny añádala a la lista actual.

Python: 55 caracteres

f=lambda l:l and[x*l[0]for x in f(l[1:])]+f(l[1:])or[1]

Genera recursivamente los productos eligiendo incluir o excluir cada número a su vez.

PARI / GP , 26 bytes

v->divisors(factorback(v))

Las versiones más largas incluyen

v->divisors(prod(i=1,#v,v[i]))

(30 bytes) y

v->divisors(fold((x,y)->x*y,v))

(31 bytes).

Tenga en cuenta que si la entrada fuera una matriz de factorización en lugar de un conjunto, 18 bytes podrían guardarse usando divisorssolo. Pero convertir un conjunto en una matriz de factorización parece tomar más de 18 bytes. (Puedo hacerlo en 39 bytes directamente como v->concat(Mat(v~),Mat(vectorv(#v,i,1)))24 bytes multiplicando y re-factorizando v->factor(factorback(v)), ¿alguien puede hacerlo mejor?)

Sabio - 36 34

Esencialmente, lo mismo que la solución de Martin Büttner , si lo entiendo correctamente. Como lo mencioné en un comentario, podría publicarlo como respuesta.

lambda A:map(prod,Combinations(A))

Esta es una función anónima, que por ejemplo se puede llamar de la siguiente manera:

(lambda A:map(prod,Combinations(A)))([2,3,5,7])

J (20)

Esto resultó más de lo que esperaba o esperaba. Aún así: ¡más corto que Haskel!

*/@:^"1#:@i.@(2&^)@#

Uso:

    f=:*/@:^"1#:@i.@(2&^)@#
    f 2 3 5 7
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210

Esto funciona para cualquier conjunto de números, no solo primos. Además, los números primos pueden tener un tamaño ilimitado, siempre que la matriz tenga el postfix x:2 3 5 7x

05AB1E , 2 bytes

æP

Pruébalo en línea!

Explicación

æ   # powerset
 P  # product

R, 56 bytes

r=1;for(i in 1:length(s))r=c(r,apply(combn(s,i),2,prod))

Estoy considerando aquí que s es el conjunto (y una lista). Estoy seguro de que puede hacerse aún más corto. Ya vere.

PHP, 97 bytes

<?for(;$i++<array_product($a=$_GET[a]);){$t=$i;foreach($a as$d)$t%$d?:$t/=$d;if($t<2)echo"$i\n";}