Fatoração de matrizes

13

Dada uma matriz de números inteiros positivos, produz uma matriz estável dos fatores primos distintos desses números inteiros. Em outras palavras, para cada número inteiro na entrada em ordem, obtenha seus fatores primos, classifique-os e acrescente quaisquer números primos que ainda não estejam na saída.

Casos de teste

[1,2,3,4,5,6,7,8,9,10] -> [2,3,5,7]
[10,9,8,7,6,5,4,3,2,1] -> [2,5,3,7]
[100,99,98,1,2,3,4,5] -> [2,5,3,11,7]
[541,60,19,17,22] -> [541,2,3,5,19,17,11]
[1,1,2,3,5,8,13,21,34,45] -> [2,3,5,13,7,17]
[6,7,6,7,6,7,6,5] -> [2,3,7,5]
[1] -> []
[8] -> [2]
[] -> []

A saída pode ser como uma matriz ou lista de números inteiros ou seqüências de caracteres, saída delimitada ou qualquer outro meio padrão de gerar uma lista ordenada de números.

Isso é código-golfe , então a resposta mais curta em bytes vence.

code-golf array-manipulation primes Stephen
fonte
Sandbox
Stephen
5
Esse é um daqueles desafios que eu acho que é "simples demais". Quase todas as respostas se parecerão com uma destas: (a) um loop sobre a entrada e Ye Olde Prime Factorization Code com um apêndice condicional; (b) uma cadeia de quatro embutidos. Simplesmente não há muito espaço para criatividade. Talvez as respostas me provem erradas, mas duvido. Há muito pouco mais no golfe do que a fatoração principal aqui, e isso foi feito até a morte.
Lynn
1
@ Lynn é trivial para jogadores de golfe, mas não trivial para quase todo o resto. Não tenho certeza se isso é motivo de trivialidade aqui: /
Stephen
Você pode me dizer quais são "os principais fatores distintos" de 1?
J42161217
1
@DigitalTrauma Yes. Caso contrário, seria apenas "produzir o conjunto de todos os fatores primos da entrada"
Stephen

Respostas:

9

05AB1E , 3 bytes

Saídas como uma lista de Strings.

f˜Ù

Experimente online!

2sable , 3 bytes

Sim, isso também funciona no 2sable. Também retorna uma lista de Strings.

f˜Ù

Experimente online!

Mr. Xcoder
fonte
6
Hah ... f U. Adoro.
Magic Octopus Urn
@MagicOctopusUrn Obrigado :-)
Sr. Xcoder
5

Casca , 3 bytes

1 byte salvo graças ao @Zgarb .

uṁp

Experimente online!

Explicação

Programa completo.

  p Fatores primários de cada um.
 ṁ Mapeie a função sobre a lista e concatene o resultado.
Única.
Mr. Xcoder
fonte
3
Σ†pode ser ṁ.
Zgarb 29/08/19
@ Zgarb Muito obrigado. Como você pode dizer, é minha primeira resposta Husk sempre :)
Mr. Xcoder
É bom ver novas pessoas usando Husk. :)
Zgarb
1
@Zgarb Parece muito bom (especialmente quando se outgolfs Jelly: P)
Mr. Xcoder
5

Utilitários Bash + GNU, 37

  • 21 bytes salvos graças a @muru (uau!)
factor|tr \  \\n|awk '!/:/&&!a[$0]++'

Experimente online .

Trauma Digital
fonte
1
Eu acho que isso nl|sort|...pode ser feito usando awk: awk '!a[$0]++'(imprima se não for visto antes; portanto, a ordem nunca será perdida), economizando 15 bytes. Em seguida, o sedcomando pode ser eliminado usando um comando um pouco mais longo awk: factor|awk '!/:/&&!a[$0]++' RS='[ \n]+'(divida registros em espaços e novas linhas, ignore registros com :), economizando outros 4 bytes.
muru
1
Eu só percebi que pode salvar mais dois bytes no comentário anterior utilizando tr: factor|tr \ \\n|awk '!/:/&&!a[$0]++'(que é dois espaços após a primeira barra invertida)
Muru
@muru awesome - obrigado! (Eu não teria sido perturbado se você tinha postado isso como sua própria resposta, que significativamente out-golfed meu original)
Digital Trauma
4

MATL , 6 bytes

"@Yfvu

Experimente online!

Explicação:

"      % Loop over input
 @     % Push the array element
  Yf   % Prime factors
    v  % Concatenate entire stack vertically (does nothing the first iteration)
     u % Stably get distinct (unique, in MATLAB terminology) elements. Does so every loop but this is code golf, not fastest code.

Boatos interessantes de MATL: geralmente, todas as funções se aplicam a vetores (matrizes) com a mesma facilidade. Mas, nesse caso, o número de fatores é variável para cada entrada, e o Matlab e, por extensão, o MATL geralmente lidam apenas com matrizes quadradas, então tive que usar um loop for" .

Além disso, o MATL possui dois principais operadores de concatenação: he v, concatenação horizontal e vertical. O comportamento deles difere significativamente: vconcatena a pilha inteira, mesmo que tenha apenas um elemento como em nossa primeira iteração. husa exatamente dois elementos e falhará se apenas um estiver presente, tornando-o inadequado para este aplicativo.

Sanchises
fonte
4

Braquilog , 6 bytes

ḋᵐ↔ᵐcd

Experimente online!

Braquilog , 6 bytes

ḋᵐoᵐcd

Experimente online!

Explicação

ḋᵐ Mapa com decomposição principal (que retorna os fatores em ordem inversa).
  ↔ᵐ Inverta cada (ou faça o pedido de cada).
    c Concatenar (nivelar).
     d Desduplicar.
Mr. Xcoder
fonte
3

PowerShell , 102 bytes

param($x)$a=@();$x|%{$a+=(2..($z=$_)|?{!($z%$_)-and'1'*$_-match'^(?!(..+)\1+$)..'}|sort)};$a|select -u

Experimente online!

(Empresta a idéia de fatoração da resposta de TessellatingHeckler sobre "Ponha-se atrás de mim, Satanás-Prime!")

Recebe a entrada como uma matriz literal $x. Cria uma nova matriz vazia $a. Loops over $x. Cada iteração faz um loop do 2número atual, verificando se esse é um fator -andprimo e, em seguida, |sorta saída dele, e anexado a$a . Quando terminar de atravessar $x, nós então a saída $a, mas |selectapenas os -unúmeros nique dos mesmos. Isso explora o fato de que o uniqueify vai da esquerda para a direita, mantendo a primeira ocorrência, que corresponde à descrição do problema. Esses números são deixados no pipeline e a saída é implícita.

— AdmBorkBork
fonte
3

CJam, 11 bytes

{:mfe__&1-}

Função que recebe matriz de entradas e gera uma matriz de entradas.

Versão de teste

— geokavel
fonte
Como diferenciaria a saída com vários caracteres? Pelo menos para o meu teste (online), ele gera uma string, não uma matriz de entradas.
— Stephen
Como função, seu tipo de dados de saída é uma matriz de entradas. O CJam imprime automaticamente essa pilha e imprime matrizes sem delimitadores. Não sei se isso é bom o suficiente para seus propósitos. Se você deseja delímetros, adicione S*dentro do colchete próximo.
— geokavel
Acredito que os langs baseados em pilha possam produzir pelo ToS de qualquer maneira, então está tudo bem, eu só estava pensando. Obrigado.
— Stephen
2

Mathematica, 64 bytes

Select[DeleteDuplicates[First/@FactorInteger@#~Flatten~1],#>1&]&

entrada

[{100, 99, 98, 1, 2, 3, 4, 5}]

J42161217
fonte
Select[#&@@@Gather[#&@@@Join@@FactorInteger@#],#>1&]&
matrix89
2

Haskell, 77 bytes

import Data.List
x!y|y>x=[]|x`mod`y<1=y:(x`div`y)!y|1<2=x!(y+1)
nub.((!2)=<<)

Explicação:

  • o x!yoperador retorna uma lista de todos os fatores primos xmaiores ou iguais ay
  • a (!2)função retorna uma lista de todos os fatores primos de seu argumento
  • a função na última linha implementa a funcionalidade necessária

Experimente online.

Cristian Lupascu
fonte
2

Braquilog , 6 bytes

ḋᵐoᵐcd

Experimente online!

Explicação

ḋᵐ         Map prime decomposition
  oᵐ       Map order
    c      Concatenate
     d     Remove duplicates
Fatalizar
fonte
Fais para [10,9,8,7,6,5,4,3,2,1]. Deve ser [2, 5, 3, 7], não[2, 3, 5, 7]
Sr. Xcoder 30/08
Você pode corrigir isso para +1 byte:ḋᵐoᵐcd
Sr. Xcoder 30/08/19
@ Mr.Xcoder Obrigado, corrigido. Exigência não sensorial bastante imo embora.
Fatalize 30/08/19
Não é realmente não sensorial, pois é um pouquinho, um pouquinho menos trivial. Também postei minha própria resposta, mas usei o inverso primeiro, em vez da ordem. Não sabe por que os fatores primos são gerados em ordem inversa?
Sr. Xcoder 30/08/19
@Fatize bem - o desafio não é "classificar fatores primos distintos da lista", é "iterar pela lista e anexar fatores primos distintos".
Stephen
2

Ohm v2 , 3 bytes

Mais um byter de 3 bytes (graças a idiomas com auto-vetorização).

m{U

Experimente online!

Explicação

m Fatores primos. Vetoriza-se automaticamente sobre a entrada.
 {Achatar.
  U Uniquify.
Mr. Xcoder
fonte
2

Japt , 6 bytes

mk c â

Teste-o

Explicação

Entrada implícita da matriz U. Mapeie ( m) sobre ele, obtendo os fatores ( k) de cada elemento. Achatar ( c), obter os elementos exclusivos ( â) e gerar implicitamente.

Shaggy
fonte
2

Python 3 , 128 125 116 bytes

Esta é uma solução Python pura. Sem pacotes. Agradecimentos a Halvard por salvar 9 bytes.

def f(l):y=[k for i in l for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))];print(sorted({*y},key=y.index))

Experimente online!

Python 2 , 133 127 126 bytes

def f(l):y=sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]);print sorted(set(y),key=y.index)

Experimente online!

Python 2 , 142 138 134 bytes

l=input();r=[]
for i in sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]):r+=[i]*(i not in r)
print r

Experimente online!

Muito surpreso por ainda não haver resposta em Python. Trabalhando no golfe.

Mr. Xcoder
fonte
116 bytes Python 3
Halvard Hummel
@HalvardHummel Thanks
Sr. Xcoder
2

Deorst , 16 bytes

EDkE]l1FeFPkEQE_

Experimente online!

Feito com a ajuda de @cairdcoinheringaahing na sala de bate-papo de Deorst (observe que as soluções são diferentes).

Explicação

EDkE] l1FeFPkEQE_ Programa completo.

ED Empurre a lista de divisores de cada elemento.
  k Impedir que a pilha reorganize.
   E] Achate a pilha.
     l1Fe Remova 1s da pilha (porque o caird correu e fez 1 prime!) - Deve ser removido em versões futuras do idioma.
         FP Mantenha os números primos.
           k Impedir que a pilha reorganize.
            EQ deduplicado.
              E_ Saída do resultado.
Mr. Xcoder
fonte
2

Deorst , 16 bytes

EDkE]EQFPkl1FeE_

Experimente online!

Feito com a ajuda de @ Mr.Xcoder. Isso é muito longo para uma linguagem de pseudo-golfe.

Como funciona

EDkE]EQFPkl1FeE_ - Full program, implicit input: [1,2,3,4,5]

ED               - Get divisors. Vectorizes. STACK = [[1], [1,2], [1,3], [1,2,4], [1,5]]
  k              - Turn off sorting for the next command
   E]            - Flatten the stack. STACK = [1, 1, 2, 1, 3, 1, 2, 4, 1, 5]
     EQ          - Deduplicate stack in place. STACK = [1, 2, 3, 4, 5]
       FP        - Filter by primality 1 is considered prime. STACK = [1, 2, 3, 5]
         k       - Turn off sorting for the next command
          l1     - Push 1. STACK = [1, 2, 3, 5, 1]
            Fe   - Filter elements that are equal to the last element. STACK = [2, 3, 5]
              E_ - Output the whole stack
caird coinheringaahing
fonte
1

Pyke , 4 bytes

mPs}

Experimente aqui!

mP   -   map(factorise, input)
  s  -  sum(^)
   } - uniquify(^)
Azul
fonte
Ouch, eu ninja'd-lo mal - Boa temos diferentes abordagens :)
Mr. Xcoder
: P Diferença de um byte. Eu acho que é permitido embora ou, pelo menos, de acordo com o último consenso li
Azul
Sim, respostas duplicadas, e até byte a byte são permitidas
Mr. Xcoder
1

MY, 17 bytes

⎕Ḋḟ’⊢f(‘53ǵ'ƒf(ū←

Experimente online!

Quão?

  • ⎕ entrada avaliada
  • Ḋ divisores (vetoriza / vecifica)
  • ḟ aplainar
  • ’⊢f(‘decremento, filtro, incremento (remove 1)
  • 53ǵ'a string 'P'na página de código do MY, que é o teste de primalidade. Infelizmente 0x35=53é o 16º número primo, e não há um comando para pressionar16 para a pilha> _ <.
  • ƒ Como uma função
  • f( filtrar por isso
  • ū unificar
  • ← resultado
Zacharý
fonte
1

C ++, 118 bytes

[](auto n){decltype(n)r;for(int m:n)for(int i=1,j;i++<m;){j=m%i;for(int x:r)j|=!(i%x);if(!j)r.push_back(i);}return r;}

Precisa passar a entrada em a std::vector<int>, retorna outra std::vector<int>para saída.

hvd
fonte
1

J, 10 bytes

~.(#~*),q:

Tenho certeza que algum J-er inteligente poderia tornar isso mais curto.

Gregory Higley
fonte
1

Python 2, 88 119 103 bytes

Aqui vamos nós. Com a classificação correta.

def f(l,s=[]):[s.append(x) for x in sum([list(primefac(i)) for i in l],[]) if x not in s];print s
from primefac import*

Aparentemente, não consigo fazê-lo funcionar no TIO, porque o pacote não é suportado. Ele roda na minha máquina. Aqui estão as minhas saídas de teste:

f([1,2,3,4,5,6,7,8,9,10],[])     #[2, 3, 5, 7]
f([10,9,8,7,6,5,4,3,2,1],[])     #[2, 5, 3, 7]
f([100,99,98,1,2,3,4,5],[])      #[2, 5, 3, 11, 7]
f([541,60,19,17,22],[])          #[541, 2, 3, 5, 19, 17, 11]
f([1,1,2,3,5,8,13,21,34,45],[])  #[2, 3, 5, 13, 7, 17]
f([6,7,6,7,6,7,6,5],[])          #[2, 3, 7, 5]
f([1],[])                        #[]
f([8],[])                        #[2]
f([],[])                         #[]

De alguma forma, não fui capaz de fazer a função como uma função lambda. Sempre que tento retornar a compreensão da lista, ele retorna [Nenhum, Nenhum, ...]. Se eu estou apenas negligenciando algo, alguém poderia apontar esse erro? Obrigado pelo feedback!

Editar:

Usando o algoritmo de classificação Mr. Xcoders, eu poderia reduzir o código em 16 bytes. Obrigado por essa parte.

from primefac import*
def f(l):a=sum([list(primefac(i))for i in l],[]);print sorted(set(a),key=a.index)
Simon
fonte
Isso não parece estar correto. O segundo caso de teste deve ser exibido [2, 5, 3, 7]. A ordem das saídas é importante.
Mego
sorted(set().union(*map(primefac,l)))
Alex Hall
A ordem das saídas é importante. Releia a explicação ou procure outras respostas - eu realmente não sei mais o que explicar.
Stephen
@Stephen. Rotina atualizada, com saída correta. Demorei um pouco até perceber as diferenças em cada linha. O foco durante a leitura ajuda muito.
Simon
O @Simon salva três bytes livrando-se de espaços após parênteses - s.append(x) for-> s.append(x)for, primefac(i)) for-> primefac(i))for, []) if->[])if
Stephen
1

Braingolf , 7 bytes

&(p)u=;

Experimente online!

Oh, olha, é basicamente uma cadeia de 4 embutidos

Explicação

&(p)u=;  Implicit input from commandline args
 (.)     Sandbox loop, sandboxes each item in a separate stack and runs the
         code within the loop.
&        Append the entire sandboxed stack when loop ends, rather than only the
         top of stack after each iteration
  p      Prime factors
    u    Unique
     =   Print stack
      ;  Suppress implicit output
Skidsdev
fonte
Falha em [10,9,8,7,6,5,4,3,2,1]. - A ordem é importante: você deve retornar em [2, 5, 3, 7]vez de [2, 3, 5, 7].
Mr. Xcoder
Você pode corrigir isso por -1 byte . Uma vez que Ksó faz mal aqui.
Mr. Xcoder
@ Mr.Xcoder oh certo, sim, não sabia que eles deveriam estar em ordem de ocorrência, não em ordem crescente. Corrigido
Skidsdev