definir interseção de duas listas

10

Seu objetivo é calcular a interseção definida de duas listas de números inteiros. A interseção é definida como o único grupo não ordenado de números inteiros encontrado pelo menos uma vez na lista de entradas.

Entrada

A entrada pode estar em qualquer formato desejado (parâmetro de função, stdio, etc.) e consiste em duas listas de números inteiros. Muitos não assumem nada sobre cada lista, exceto que eles podem conter um número não negativo de números inteiros (ou seja, eles não são classificados, possivelmente podem conter duplicatas, podem ter comprimentos diferentes e podem até estar vazios). Supõe-se que cada número inteiro se encaixe no tipo de número inteiro assinado nativo do seu idioma, pode ter mais de 1 dígito decimal e está assinado.

Exemplo de entrada:

1 4 3 9 8 8 3 7 0
10 1 4 4 8 -1

Resultado

A saída é qualquer lista de números inteiros representando a interseção definida das duas listas para qualquer formato desejado (valor de retorno, stdio, etc.). Não há requisito para que a saída seja classificada, mas você pode fornecer uma implementação que sempre é classificada. A saída deve formar um conjunto não ordenado válido (por exemplo, não deve conter valores duplicados).

Exemplos de casos de teste (observe que a ordem da saída não é importante):

As duas primeiras linhas são as listas de entrada, a terceira linha é a saída. (empty)denota a lista vazia.

(empty)
(empty)
(empty)

1000
(empty)
(empty)

3 1 2 4 3 1 1 1 1 3
3 1 -1 0 8 3 3 1
1 3

1 2 1
3 3 4
(empty)

Pontuação

Isso é código de golfe; a resposta mais curta em bytes vence.

Furos de loop padrão são proibidos. Você pode usar quaisquer recursos internos não projetados para operações do tipo conjunto.

Recursos internos proibidos:

  • definir criação / remover duplicatas
  • definir diferença / interseção / união
  • Teste de associação generalizada (por exemplo, algo semelhante à inpalavra - chave em Python, indexOffunções semelhantes, etc). Observe que o uso de construções "foreach item in list" é permitido (supondo que elas não violem nenhuma das outras restrições), apesar do Python reutilizar a inpalavra-chave para criar essa construção.
  • Esses embutidos proibidos são "virais", ou seja, se houver um embutido maior contendo algum desses sub-recursos, é igualmente proibido (por exemplo, filtragem por associação em uma lista).

Quaisquer embutidos que não estejam na lista acima são permitidos (por exemplo, classificação, teste de igualdade de números inteiros, inclusão / remoção de lista por índice, filtragem etc.).

Por exemplo, pegue os seguintes dois trechos de exemplo (código semelhante ao Python):

# prohibited: filters by testing if each value in tmpList is a member of listA
result = tmpList.filter(listA)

# ok: filtering by a lambda which manually iterates over listA and checks for equality
def my_in_func(val, slist):
    for a in slist:
        if(val == a):
            return True
    return False
result = filter(lambda v: my_in_func(val, listA), tmpList)

Você pode implementar qualquer um desses recursos semelhantes a um conjunto e eles contarão para sua pontuação.

Sua solução deve ser concluída em um período de tempo razoável (digamos, menos de um minuto em qualquer hardware que você tenha para duas listas com comprimento de 1000 cada).

helloworld922
fonte
5
A propósito, confusão e falta de comunicação são comuns no X sem Y , e é por isso que elas são oficialmente uma das coisas a evitar ao escrever desafios .
Dennis
2
@ Dennis Sim, acho que esse problema realmente se tornou um dos seguintes :( Quando o escrevi pela primeira vez, eu esperava que pudesse ser um problema interessante, mas assim que comecei a elaborar um conjunto de regras, eu deveria ter acabado com o desafio.
precisa
É permitido um built-in que execute a codificação de duração da execução?
Isaacg
Isso deveria estar bem.
precisa
11
Pode haver duplicatas na saída?
Adám 8/03/16

Respostas:

7

Haskell, 45 42 bytes

y#(e:s)=[e|any(==e)y,all(/=e)s]++y#s
_#x=x

Experimente online!

Edit: -2 bytes graças a Ørjan Johansen, -1 byte graças a @dfeuer.

nimi
fonte
Isso é 2 bytes mais curto com recursão explícita.
Ørjan Johansen
@ ØrjanJohansen, mais 1 .
Dfeuer #
4

MATL , 18 bytes

YY_iti!=Xa)hStdfQ)

Experimente online!

Isso funciona em duas etapas. Primeiro, a interseção é calculada, possivelmente com duplicatas. Isso se baseia na comparação de todos os elementos de uma matriz com todos os elementos da outra e na manutenção dos elementos da primeira que estão presentes na segunda.

Em seguida, as duplicatas são removidas. Para isso, a matriz da etapa anterior é classificada e as entradas são mantidas se diferentes da anterior. Um -infvalor é anexado para que o primeiro valor (ou seja, o mais baixo) não seja perdido.

YY_                 % push -infinity
   it               % take first input. Duplicate
     i!             % take second input. Transpose
        =           % test all combinations of elements of the two inputs for equality
        Xa          % row vector that contains true for elements of first array that 
                    % are present in the second, possibly duplicated
          )         % index into first array to keep only those elements. Now we need
                    % to remove duplicates
           h        % append -infinity
            S       % sort
             tdf    % duplicate. Find entries that differ from the preceding
                Q)  % add 1 and index into array to keep only non-duplicates
Luis Mendo
fonte
4

Gelatina, 13 bytes

=S¥Ðf
ṂrṀ{ç³ç

Experimente online!

Como funciona

ṂrṀ{ç³ç  Main link. Arguments: A (list 1), B (list 2)

Ṃ        Yield m, the minimum of A.
  Ṁ{     Yield M, the maxmimum of A.
 r       Create an inclusive range from m to M.
    f³   Apply the helper link with right argument A.
      f  Apply the helper link with right argument B.


=S¥Ðf    Helper link. Arguments: n (integer in range), L (list, A or B)

=        Test all elements of L for equality with n.
 S       Add the results.
  ¥      Combine the two previous links into a dyadic chain.
   Ðf    Filter by the result of the sums.
Dennis
fonte
@isaacg Corrigido agora.
Dennis
3

golflua , 68 caracteres

\f(a,b)k={}~@_,v p(a)~@_,w p(b)?w==v k[w]=w$$$~@_,v p(k)I.w(v," ")$$

que é chamado como

> f({1,2,3,4},{3,4,5})
3 4
> f({3,1,2,4,3,1,1,1,1,3},{3,1,-1,0,8,3,3,1})
3 1

Em Lua normal, isso seria

function foo(a,b)
   local k={}
   for i,v in pairs(a)
      for j,w in pairs(b)
         if v==w then
            k[v] = v
         end
      end
   end
   for i,v in pairs(k)
      print(v," ")
   end
end

Então, basicamente, eu estou iterando sobre cada elemento das duas tabelas e armazenando apenas os valores equivalentes. Usando o valor como a chave ( k[w]=w), estou eliminando todas as duplicatas. Em seguida, produzimos a nova tabela iterando sobre o índice e o valor depairs

Kyle Kanos
fonte
3

JavaScript (ES6), 66 bytes

(a,b)=>a.filter((e,i)=>b.some(f=>e==f)&a.slice(0,i).every(f=>e-f))

Sem usar indexOf, pois não estou convencido de que seja permitido.

Neil
fonte
3

Pitão, 12 11 bytes

eMrSsq#RQE8

Demonstração

Explicação:

eMrSsq#RQE8
               Implicit: Q is one of the lists.
     q#RQE     For every element in the first list, filter the second list on
               equality with that element.
    s          Concatenate. We now have the intersection, with duplicates.
  rS      8    Sort and run length encode, giving counts and elements.
eM             Take just the elements.
isaacg
fonte
A classificação e rle economizam um byte.
Jakube
@Jakube Eu diria que rle é um builtin que remove duplicatas.
Isaacg
Ele só remove duplicatas se você as classificar antes e remover as contagens da regra posteriormente. É um pouco em uma área cinzenta, mas acho que está usando um dicionário. É basicamente um conjunto que armazena dados adicionais para cada elemento.
Jakube 6/16
@Jakube OP diz que está tudo bem. Obrigado!
Isaacg 08/03
2

bash + núcleo GNU, 184 bytes

[ -z "$1" ] && exit
p='{if(a[$0]++==0)print $0}'
while read A; do
while read B; do
[ $A = $B ] && echo $A
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")

Invocação:

./codegolf.sh '12 4 654 12 3 56' '4 4 56 33 3 3 3'

Resultado:

4
56
3

Nenhuma saída se a interseção estiver vazia. Este script não classifica e verifica a integridade se o primeiro conjunto estiver vazio. Explicação:

[ -z "$1" ] && exit  # Exit if first set is empty
p='{if(a[$0]++==0)print $0}' # The AWK program we will use
while read A; do   # read the list with two
while read B; do   # encapsulated loops
[ $A = $B ] && echo $A   # if they match, then print
done < <(grep -oP '\d*'<<<$1|awk "$p")
done < <(grep -oP '\d*'<<<$2|awk "$p")
# the process substitution greps the numbers and pipes them to awk. Our awk program makes them unique without sorting; it uses associative arrays with index names same as lines (our numbers here).

Bônus a saber: você pode mudar grep -o .para fazer isso com seqüências aleatórias em vez de números.

rexkogitans
fonte
2

Perl 6, 26 37 bytes

{%(@^a.grep(any(@^b)):p.invert).keys}

uso

> my &f = {%(@^a.grep(any(@^b)):p.invert).keys}
-> @a, @b { #`(Block|559823336) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
(1 3)

Resposta não competitiva atrevida

> [3,1,2,4,3,1,1,1,1,3]  [3,1,-1,0,8,3,3,1]
set(3, 1)

ou se você gosta de uma ffunção chata e velha

> my &f = &infix:<∩>
sub infix:<∩> (|p is raw) { #`(Sub+{<anon|130874592>}+{Precedence}|102325600) ... }
> f([3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1])
set(3, 1)
Teclas de atalho
fonte
Eu atualizei a minha resposta não usar .unique
Teclas de atalho
11
Você realmente não precisa invertse você pegar os valores. 24 bytes
Jo King
2

Retina , 63 bytes

As duas últimas linhas removem duplicatas. A entrada são duas listas delimitadas por espaço, separadas por vírgula. A saída é delimitada por espaço em branco.

+`( -?\d+)\b(.*,.*)\1\b
$1_$2
-?\d+\b|_|,

+`(-?\d+)(.*)\1
$1$2

Experimente online

Se duplicatas na saída forem permitidas, meu programa será de 42 bytes.

mbomb007
fonte
2

Jq 1.5 , 99 bytes

def f(a;b):(a+b|min)as$m|[range($m;a+b|max)|[]]|.[a[]-$m][0]=1|.[b[]-$m][1]=1|.[[[1,1]]]|map(.+$m);

Expandido

def f(a;b):
     (a+b|min) as $m         # find smallest value in either array
   | [range($m;a+b|max)|[]]  # create array of [] for indices [min,max]
   | .[ a[]-$m ][0]=1        # store 1 in [0] at corresponding indices of a
   | .[ b[]-$m ][1]=1        # store 1 in [1] at corresponding indices of b
   | .[[[1,1]]]              # find all the indices where we stored a 1 for a and b
   | map(.+$m)               # convert back from indices to values
;

Isso evita o uso de {}objetos e, como o jq não possui operações de bit, ele os emula com uma matriz.

Experimente online!

jq170727
fonte
2

Axioma, 411 bytes

b(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)
f(a:List INT,b:List INT):List INT==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;repeat(i>#x=>break;v:=x.i;binSearch(v,y)=0=>(i:=i+1);r:=concat(r,v);while i<=#x and x.i=v repeat i:=i+1);r)

ungolf e teste

--suppose v.1<=v.2<=....<=v.#v as the default function sort() produce
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione 
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v
    repeat
       l>h=>break
       m:=(l+h)quo 2
       x<v.m=>(h:=m-1) 
       x>v.m=>(l:=m+1)
       return m
    0

--N*log(N)+n*log(n)+N*n*log(n) so it is N*n*log(n) or n*N*log(N)
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1
    repeat
        i>#x=>break
        v:=x.i
        binSearch(v,y)=0=>(i:=i+1)
        r:=concat(r,v)
        while i<=#x and x.i=v repeat i:=i+1
    r

(5) -> f([],[])
   (5)  []
                                                       Type: List Integer
(6) -> f([1000],[])
   (6)  []
                                                       Type: List Integer
(7) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (7)  [1,3]
                                                       Type: List Integer
(8) -> f([1,2,1],[3,3,4])
   (8)  []
                                                       Type: List Integer
RosLuP
fonte
2

Axioma, 257 bytes

W(x,y)==>while x repeat y;f(a,b)==(r:List INT:=[];#a*#b=0=>r;x:=sort(a);y:=sort(b);i:=1;j:=1;repeat(j>#y=>break;W(i<=#x and x.i<y.j,i:=i+1);i>#x=>break;W(j<=#y and y.j<x.i,j:=j+1);j>#y=>break;v:=y.j;if x.i=v then(r:=concat(r,v);W(j<=#y and y.j=v,j:=j+1)));r)

Isso sem o uso de binsearch ... Mas eu não conheço o grande O ... Unglofed e resultados:

--N*log(N)+n*log(n)+???
ListIntersection(a:List INT,b:List INT):List INT==
    r:List INT:=[];#a*#b=0=>r
    x:=sort(a);y:=sort(b)
    i:=1;j:=1
    repeat
        j>#y=>break
        while i<=#x and x.i<y.j repeat i:=i+1
        i>#x=>break
        while j<=#y and y.j<x.i repeat j:=j+1
        j>#y=>break
        v:=y.j;if x.i=v then 
                        r:=concat(r,v)
                        while j<=#y and y.j=v repeat j:=j+1
    r

(3) -> f([3,1,2,4,3,1,1,1,1,3],[3,1,-1,0,8,3,3,1])
   (3)  [1,3]
                                                       Type: List Integer
(4) -> f([],[])
   (4)  []
                                                       Type: List Integer
(5) -> f([1,2,1],[3,3,4])
   (5)  []
                                                       Type: List Integer

Não foram executados muitos testes, portanto podem ser corrigidos ...

RosLuP
fonte
2

Gelatina , 12 bytes

pEÐfḢ€ĠḢ€$ị$

Experimente online!

HyperNeutrino
fonte
Em Tio 3,1,2,4,3,1,1,1,1,3 de entrada e de entrada 3 retornar a saída [1,2,3] em vez de [3]
RosLuP
@RosLuP Tente em [3]vez de3
HyperNeutrino 6/17
Seria bom, na minha opinião, se o resultado da interseção de 2 listas retornar (como outros casos) [] se o resultado for nulo, [1] se 2 listas tiverem 1 em comum
RosLuP
@RosLuP Não posso evitar, é assim que a Jelly produz. Vazio para []e o elemento para listas singleton. Você pode ir para a página de wiki (átomos) e anexar o Python stringify embutido, mas que faz com que a minha resposta mais longa e rigorosa I / O é burro
HyperNeutrino
Seria bom para mim se ele aceitasse apenas a lista de entrada da maneira [] (exemplo [1], [1,2,3] [], [], [] etc)) e exibisse a saída da lista apenas da maneira da lista [] (como entrada). Se os parênteses da lista forem {} ou (), repita a fala acima para a correta. Isto é apenas para o que eu penso, a questão possivelmente dizer o contrário e está tudo ok
RosLuP
2

Casca , 9 bytes

mo←←kIfE*

Experimente online!

m            Map
 o←←         taking the first element from the first element
    kI       over lists of identical values from
        *    the Cartesian product of the two input lists
      f      filtered by
       E     both elements of a pair being equal.

Observando o código-fonte da Husk no GitHub, k("keyon") é implementado como a composição da classificação da lista e do agrupamento de valores adjacentes, portanto, embora eu não consiga encontrar a implementação do "groupOn", é provável que seja seguro assumir que ele não é ' Não faça nada instável, já que Haskell é uma linguagem funcional e o agrupamento de valores iguais adjacentes é uma operação bastante simples de reduzir sobre uma lista vinculada. (Eu posso encontrar a implementação do koutro tipo de assinatura "keyby", que eu poderia usar aqui mudando Ipara =, mas não conheço Haskell, então não sei dizer exatamente como ele funciona.)

Além disso, uma boa e pequena resposta Brachylog que eu criei antes de perceber que operações de todos os tipos eram proibidas: ⟨∋∈⟩ᵘ

String não relacionada
fonte
2

R, 141 83 bytes

l=sapply(strsplit(readLines(file("stdin"))," "),as.numeric)
r=rle(sort(unlist(l)))[[2]]
r[sapply(r,function(x)any(x==l[[1]])&any(x==l[[2]]))]

Melhorado por Giuseppe

function(a,b){r=rle(sort(c(a,b)))[[2]];r[sapply(r,function(x)any(x==a)&any(x==b))]}

Experimente on-line aqui aqui

db
fonte
Isso não parece funcionar. Provavelmente, estou tentando usá-lo errado, então talvez você deva fornecer um link para Experimente Online! mostrando como usá-lo e demonstrando que cumpre os requisitos do desafio. (Uma explicação sobre a resposta também não faria mal.)
String não relacionada
você não pode assumir entradas ae bestá predefinido, deve aceitar as entradas, assumindo-as como argumentos de função ou a partir de STDIN.
Giuseppe
11
Acho Golfier seria apenas para fazer esta função, como esta
Giuseppe
11
@db O "cabeçalho" nomeia a função anônima definida na seção "Código" (funções anônimas são perfeitamente aceitáveis), e o rodapé a chama. As seções Cabeçalho, código e rodapé são todos um pedaço de código, mas apenas a parte no "Código" conta seção de bytes :-)
Giuseppe
1

Python3, 51 bytes

lambda a,b:[v for v in a if{n:1 for n in b}.get(v)]

Se as listas de entrada puderem conter duplicatas:

Python3, 67 bytes

lambda a,b:list({v:1 for v in a if {n:1 for n in b}.get(v)}.keys())
PieCot
fonte
1

PHP ,78, 77 bytes

function($a,$b){foreach($a as$x)foreach($b as$y)$x==$y?$c[$x]=$x:0;return$c;}

Experimente online!

Sem frescura, mas em conformidade com as regras (eu acho).

Resultado

[], []
[]

[1000], []
[]

[3,1,2,4,3,1,1,1,1,3], [3,1,-1,0,8,3,3,1]
[3,1]

[1,2,1], [3,3,4]
[]
640KB
fonte