Declaração de problema

Dado um conjunto de primos únicos e consecutivos (não necessariamente incluindo 2), gere os produtos de todas as combinações das primeiras potências desses primos - por exemplo, sem repetições - e também 1. Por exemplo, dado o conjunto {2, 3, 5, 7}, você produz {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

Observe que, se a cardinalidade do seu conjunto de entradas for k, isso fornecerá 2 ^ k membros no seu conjunto de saída.

Regras / Condições

1. Você pode usar qualquer idioma. Aponte para a menor contagem de caracteres do código-fonte.
2. Sua solução deve ser um programa completo ou uma função completa. A função pode ser anônima (se o seu idioma suportar funções anônimas).
3. Sua solução deve oferecer suporte a produtos de pelo menos 2 ^ 31. Não se preocupe em detectar ou manipular excesso de número inteiro se você receber números passados ​​cujo produto é ótimo demais para representar. No entanto, indique os limites dos seus cálculos.
4. Você pode aceitar uma lista ou um conjunto e produzir uma lista ou um conjunto. Você pode assumir que a entrada está classificada, mas não é necessário produzir uma saída classificada.

fundo

Quando ou por que isso é útil? Um local em que é muito útil é gerar uma tabela de multiplicadores para competir em paralelo em um algoritmo de fatoração inteiro conhecido como Fatoração de Formas Quadradas. Lá, cada multiplicador ímpar que você tenta diminui a probabilidade de o algoritmo falhar (para encontrar um fator) em aproximadamente 50% em semiprimes rígidos. Portanto, com o conjunto de primos geradores {3, 5, 7, 11}, que produz um conjunto de 16 multiplicadores de teste para correr em paralelo, o algoritmo falha aproximadamente 2 ^ –16 do tempo em semiprimes rígidos. Adicionar 13 à lista de números primos produz um conjunto de 32 multiplicadores de teste, reduzindo a chance de falha para aproximadamente 2 ^ –32, proporcionando uma melhoria drástica no resultado sem nenhuma despesa computacional adicional (porque mesmo com o dobro do multiplicador correndo em paralelo, em média, ainda encontra a resposta no mesmo número total de etapas).

Pure Bash, 32 bytes

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

Lê a lista de entrada (separada por espaço único) passada como um argumento da linha de comandos.

Três expansões de shell diferentes são usadas:

1. ${1// /\}*{1,}é uma expansão de parâmetro que substitui os espaços 2 3 5 7com }*{1,para dar 2}*{1,3}*{1,5}*{1,7. \$[{1,e }]são adicionados ao início e ao fim, respectivamente, para fornecer \$[{1,2}*{1,3}*{1,5}*{1,7}]. O \$[escape é invertido para impedir tentativas de expansão aritmética neste estágio.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}]é uma expansão de chave . Como a expansão entre chaves geralmente ocorre antes da expansão dos parâmetros , usamos a necessidade evalde forçar a expansão dos parâmetros a ocorrer primeiro. O resultado da expansão da cinta é $[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]é uma lista de expansões aritméticas , que são avaliadas para fornecer a lista de números que precisamos.

Saída:

$ ./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

Lê uma matriz (por exemplo, [2 3 5 7]) de STDIN. Experimente online.

Uma função anônima teria a mesma contagem de bytes:

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

Exemplo de execução

$ 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]

Como 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

a solução é uma função anônima:

map product.mapM(:[1])

exemplo de uso:

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

explicação:
(:[1]) é uma função que, dado um número, xretorna a lista [x,1].
mapM(:[1])é uma função que, dada uma lista de números, mapeia a função (:[1])sobre eles e retorna todas as formas possíveis para escolher um elemento de cada lista. por exemplo, mapM(:[1]) $ [3,4]primeiro mapeia a função a ser obtida [[3,1] , [4,1]]. então as opções possíveis são [3,4](escolhendo o primeiro número de ambos) [3,1] [1,4]e, [1,1]portanto, ele retorna [[3,4],[3,1],[1,4],[1,1]].

depois map productmapeia todas as opções e retorna seus produtos, que são a saída desejada.

essa função é polimórfica em seu tipo, o que significa que pode operar em todos os tipos de números. você poderia inserir uma lista Inte o resultado seria uma lista de, Intmas também poderia ser aplicado em uma lista do tipoIntegere retorne uma lista de Integer. isso significa que o comportamento de estouro não é especificado por essa função, mas pelo tipo de entrada (sistema de tipo expressivo de yay Haskell :))

Mathematica, 18 17 bytes

1##&@@@Subsets@#&

Essa é uma função anônima. Chame como

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

Atualização: C (função f), 92

Mesmo em função, essa ainda é a entrada mais longa aqui. É a primeira vez que eu passo uma matriz de comprimento desconhecido como argumento de função em C e, aparentemente, não há como uma função C saber o comprimento de uma matriz passada para ela, pois o argumento é passado como um ponteiro ( independentemente da sintaxe usada). Portanto, um segundo argumento é necessário para indicar o comprimento.

Eu mantive a saída em stdout, porque configurar uma matriz inteira e retorná-la quase certamente seria mais longa.

Obrigado a Dennis pelas dicas.

Veja a função f(92 caracteres, excluindo espaços em branco desnecessários) nos programas de teste abaixo.

Saída via 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);
}

Saída via ponteiro 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

excluindo espaços em branco desnecessários.

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 da linha de comando, saída para stdout. C não vai ganhar aqui, mas talvez eu tente converter para uma função amanhã.

Basicamente, iteramos em todas as 1<<ccombinações de números primos, com cada bit i/cassociado à presença ou ausência de um número primo específico no produto. O "loop interno" i%cpercorre os números primos, multiplicando-os de acordo com o valor de i/c.Quando i%catinge 0, o produto é emitido e, em seguida, definido como 1 para a próxima iteração "externa".

curiosamente, printf("%d ",p,p=1)não funciona (sempre imprime um 1.) Essa não é a primeira vez que vejo um comportamento estranho quando um valor é usado em a printfe atribuído posteriormente no mesmo colchete. É possível, neste caso, que a segunda vírgula não esteja sendo tratada como um separador de argumentos, mas como um 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 é uma implementação Haskell da resposta CJam do @ sudo como uma função anônima. Não superará a incrível solução Haskell do @proud haskeller, mas eu a deixarei aqui de qualquer maneira.

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

Explicação: foldr obtém uma função binária, um valor e uma lista. Em seguida, ele substitui a cada célula contras na lista por uma aplicação da função, eo fim da lista pelo valor, como este: foldr f v [a,b,c] == f a (f b (f c v)). Nosso valor é uma lista de um elemento que contém 1e a função binária é f = (=<<)(++).map.(*). Agora, fpega um número n, cria uma função (n*)que se multiplica n, cria uma função g = map(n*)que aplica essa função a todos os elementos de uma lista e alimenta essa função (=<<)(++). Aqui, (++)é a função de concatenação, e (=<<)é ligamento monádico , que neste caso leva em (++)e g, e dá uma função que leva em uma lista, aplica-seg para uma cópia e concatena os dois.

Em resumo: comece com [1]e para cada número nna lista de entrada, faça uma cópia da lista atual, multiplique tudo por ne adicione-a à lista atual.

Python: 55 caracteres

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

Gera recursivamente os produtos escolhendo incluir ou excluir cada número por vez.

PARI / GP , 26 bytes

v->divisors(factorback(v))

Versões mais longas incluem

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

(30 bytes) e

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

(31 bytes).

Observe que se a entrada fosse uma matriz de fatoração em vez de um conjunto, 18 bytes poderiam ser salvos usando-se divisorssozinhos. Mas converter um conjunto em uma matriz de fatoração parece levar mais de 18 bytes. (Eu posso fazê-lo em 39 bytes diretamente como v->concat(Mat(v~),Mat(vectorv(#v,i,1)))ou 24 bytes multiplicando e realimentando v->factor(factorback(v)), alguém pode fazer melhor?)

Sábio - 36 34

Essencialmente, o mesmo que a solução de Martin Büttner , se bem entendi. Como mencionei em um comentário, posso postá-lo como resposta.

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

Esta é uma função anônima, que pode, por exemplo, ser chamada da seguinte maneira:

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

J (20)

Isso acabou mais do que eu esperava ou esperava. Ainda: mais curto que o 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

Isso funciona para qualquer conjunto de números, não apenas números primos. Além disso, os números primos podem ter tamanho ilimitado, desde que a matriz tenha o postfix x:2 3 5 7x

05AB1E , 2 bytes

æP

Experimente online!

Explicação

æ   # powerset
 P  # product

R, 56 bytes

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

Estou considerando aqui que s é o conjunto (e uma lista). Tenho certeza de que pode ser reduzido ainda mais. Eu verei.

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";}