Contar ocorrências de um conjunto em uma lista

15

Dado um conjunto de cadeias não vazio e uma lista de cadeias, descubra quantas vezes o conjunto ocorre na lista, ou seja, quantas vezes você pode criar o conjunto com itens da lista. Cada elemento da lista pode ser usado apenas uma vez.

Dica: um conjunto é uma lista não ordenada de itens exclusivos.

Regras de entrada / saída padrão se aplicam.

Nenhuma biblioteca externa permitida. As bibliotecas padrão do compilador / intérprete estão bem. Este é o código de golfe, portanto, a solução mais curta conta.


Casos de teste:

["apple", "banana"], ["apple", "pear", "apple", "banana", "banana"] => 2

["apple", "banana"], ["apple", "pear", "apple", "banana", "apple"] => 1

["apple", "banana", "pear"], ["apple", "banana", "kiwi", "apple"] => 0

["coconut"], [] => 0

EDIT: removeu uma sentença informando que os parâmetros de entrada estão definidos no escopo local. Isso contradiz as regras de E / S padrão vinculadas acima.

Hubert Grzeskowiak
fonte
Sim, isso esclarece. No entanto, estou um pouco desligado na terceira frase. O que você quer dizer com "não lida com objetos"?
Post Rock Garf Hunter
@WheatWizard algumas linguagens não são orientadas a objetos e não conhecem o conceito de comparar objetos arbitrários.
Hubert Grzeskowiak
1
Você provavelmente deve mudar isso para orientado a objetos, porque toda linguagem que eu conheço lida com objetos de algum tipo, mesmo que os objetos sejam de classe fechada. Devo também salientar que existem muitas linguagens que também não conseguem lidar com strings.
Post Rock Garf Hunter
@ WheatWizard ok, descrição atualizada. Esse parágrafo foi feito para idiomas como C, Assembler ou Maple.
Hubert Grzeskowiak
Quais idiomas são orientados a objetos? O que eles devem usar se não forem cordas? Eu acho que a coisa mais fácil seria restringir a apenas strings. Ou, alternativamente, apenas números inteiros. Consulte este conselho sobre como usar o tipo mais simples que é suficiente.
Xnor

Respostas:

12

Python, 30 bytes

lambda s,l:min(map(l.count,s))

Experimente online!

ovs
fonte
Agradável. Não pensou em usar o mapa. Você pode economizar um pouco usando print em vez de definir um BTW lambda.
Hubert Grzeskowiak
1
@HubertGrzeskowiak A alteração de lambdapara a printeleva a contagem de bytes até 37 por causa dos dois input()s necessários.
Post Rock Garf Hunter
@WheatWizard conforme declarado no desafio, considere as entradas definidas no escopo local. Você NÃO é obrigado a ter as entradas definidas explicitamente, por exemplo, como parâmetros de função ou entradas do usuário.
Hubert Grzeskowiak
@HubertGrzeskowiak se não há nenhuma boa razão para isso, você não deve substituir os nossos padrões para a tomada de entrada e saída e os nossos padrões para submissões codegolf
OVS
@ ohs, eu não estava ciente desse post. Obrigado.
Hubert Grzeskowiak
6

Gelatina , 4 bytes

⁼þSṂ

Experimente online!

Quão?

⁼þSṂ - Main link: list theSet, list theList
 þ   - outer product using the dyadic operation:
⁼    -     is equal? (non-vectorising)
  S  - sum (vectorises) (yields the number of times each element of theSet appears in theList)
   Ṃ - minimum (can only make the minimum as a multiple)
Jonathan Allan
fonte
6

Geléia , 6 5 4 bytes

ċ@€Ṃ

Experimente online!

O primeiro argumento do programa é o conjunto e o segundo argumento é a lista.

Explicação

ċ@€Ṃ
ċ@   -- Create a link which finds the number of occurrences of 
          its left argument in its right argument (the list)
  €  -- Map this link over each element in the first argument
          of the program (the set)
   Ṃ -- Minimum value of this.

-1 byte graças a @ETHproductions

-1 byte novamente graças a @ETHproductions

fireflame241
fonte
Muito agradável! Você pode salvar um byte, combinando as ligações em uma linha: ⁹ċ$€ṂEu tenho um sentimento que pode ser feito mais curto usando o argumento direito implícito no lugar de ...
ETHproductions
Eu acho que ċ@€Ṃ funciona para salvar outro byte ... (o @inverte os argumentos para ċ)
ETHproductions
@ETHproductions Funciona corretamente tanto quanto eu testei.
precisa saber é o seguinte
Ele não existia até 12 de maio do ano passado, mas no lugar de @€(com argumentos invertidos para o programa) economiza mais um byte: Experimente on-line!
String não relacionada
6

JavaScript (ES6), 56 bytes

f=(n,h)=>Math.min(...n.map(c=>h.filter($=>$==c).length))

Experimente online

Alberto Rivera
fonte
1
Guardar 2 bytes usando uma função anônima e outro por currying os parâmetros: n=>h=>Math.min(...n.map(c=>h.filter($=>$==c).length))para 53 bytes
Shaggy
5

JavaScript (ES6), 64 bytes

(s,l)=>l.map(e=>m[s.indexOf(e)]++,m=s.map(e=>0))&&Math.min(...m)

Assume ambos se lsão matrizes de objetos. Usa a igualdade estrita de JavaScript para comparações, portanto, por exemplo, [] === []é falso.

Neil
fonte
Solução muito interessante. Por favor, devolva ou imprima o resultado. AFAIK isso retorna uma função anônima.
Hubert Grzeskowiak
2
@HubertGrzeskowiak O código mostrado é avaliado para uma função anônima. Quando chamada, a função retorna a contagem conforme desejado.
194 Neil
4

Haskell , 37 34 bytes

Obrigado a @Laikoni por remover três bytes.

s#l=minimum[sum[1|y<-l,y==x]|x<-s]

Ligue com (set::[a]) # (list::[a])onde aé derivado qualquer tipo Eq.

Julian Wolf
fonte
Ao invés de length[y|y<-l,y==x] você pode usar sum[1|y<-l,y==x].
Laikoni
@Laikoni, você tem certeza disso? Eu acho que precisaria usar algo comosum[1|y<-l,y==x,_<-y] , que sai para dois bytes longo Eu definitivamente poderia estar faltando alguma coisa lá, embora
Julian Lobo
Não importa, você está definitivamente certo. Boa decisão.
Julian Lobo
3

CJam , 11 bytes

q~f{\e=}:e<

Experimente online!

Explicação

q~           e# Read and eval the input
  f{\e=}     e# Map each item in the set to the number of times it appears in the list
        :e<  e# Find the minimum of the resulting list
Gato de negócios
fonte
3

Mathematica, 24 bytes

Min[#/.Rule@@@Tally@#2]&

Função pura, tendo duas listas como argumentos na ordem sugerida e retornando um número inteiro não negativo. Tallyconta quantas ocorrências de cada símbolo ocorrem na lista de entrada e#/.Rule@@@ converte cada elemento do conjunto de entradas no número correspondente de ocorrências.

Greg Martin
fonte
3

T-SQL, 62 59 bytes

A versão anterior não funcionava para conjuntos sem correspondências

select top 1(select count(*)from l where l=s)from s order by 1

Com s e l como tabelas e colunas com o mesmo nome da tabela

select top 1         -- return only the first result
    (select count(*) -- count of rows
     from l          -- from table l
     where l=s)      -- for each l equal
from s               -- to each from s
order by 1           -- sort by count ascending
MickyT
fonte
3

Rápido, 39 bytes

s.map{w in l.filter{$0==w}.count}.min()

explicação:

s.map{} passa por cada palavra em se produzirá uma série de contagens

w in nomeia a palavra mapeada para uso no próximo filtro

l.filter{} aplica um filtro à matriz l

$0==w é a condição de filtro que corresponde à palavra w

.count fornece o número de elementos de l que atenderam à condição

.min() retorna a contagem mais baixa no resultado mapeado

user68380
fonte
1
Bem-vindo ao PPCG! Adicionei formatação de código para sua solução. Você pode fazer isso anexando 4 espaços às linhas que contêm código.
Mego
3

APL (Dyalog) , 9 bytes

⌊/+/⎕∘.≡⎕

Experimente online!

 obter entrada avaliada (lista de strings)

⎕∘.≡ obter entrada avaliada (conjunto de cadeias não vazio) e criar tabela de equivalência

+/ adicionar

⌊/ mínimo em

Adão
fonte
2

Perl 6 ,  37  18 bytes

37.

{+(($_=@^a⊍@^b)≽@a)&&.values.min}

Tente

Expandido:

{
  +( # turn into a 0 if False

    (
      $_ =        # store into $_ the result of
        @^a  @^b # use the baggy multiplication operator
    )  @a        # is that the baggy superset of the set
  )

  &&          # if that is True

  .values.min # get the minimum value from the Bag in $_
}

Consulte Conjuntos, malas e misturas para obter mais informações.


18

{@^b.Bag{@^a}.min}

Tente

Explicação:

@^b.Bagcrie um saco a partir da
{@^a}chave de valores nesse saco (retorna uma lista de contagens) e
.minobtenha o valor mínimo da lista resultante


Brad Gilbert b2gills
fonte
Respostas simples, mas nenhuma delas se parece com funções / programas completos
Julian Wolf
@JulianWolf: Eu tive a impressão de que snippets eram permitidos com base nas instruções “Considere as duas entradas definidas no escopo atual como s e l”. E “Você não precisa definir uma função.” Fui e editei de qualquer maneira .
precisa saber é o seguinte
Ah, você está completamente certo. Isso deve ter sido editado na pergunta depois que eu a li. De qualquer forma, gosto mais da estética desta versão do que a anterior - a sintaxe de Perl sempre será um mistério para mim.
Julian Lobo
@ JulianWolf Este não é realmente um bom exemplo de código Perl 6. Eu recomendaria assistir a 1hr talk de Ovid, Perl 6 - Por que as pessoas estão tão empolgadas , ou olhar a guia Recursos no Perl6.org .
precisa saber é o seguinte
Sim, desculpe pela confusão. Este é o meu primeiro desafio e eu não sabia que já existem regras para entrada e saída. Eu mudei porque a maioria das respostas estava usando essas regras, mesmo que não fosse necessária.
Hubert Grzeskowiak
2

Axioma, 42 bytes

f(a,b)==reduce(min,[count(x,b)for x in a])

código de teste e resultados

(28) -> f(["1","2"], ["1", "2", "1", "1", "7"])
   (28)  1
                                                    Type: PositiveInteger
(29) -> f(["apple","banana"],["apple","pear","apple","banana","banana"])
   (29)  2
                                                    Type: PositiveInteger
(30) -> f(["apple","banana"],["apple","pear","apple","banana","apple"])
   (30)  1
                                                    Type: PositiveInteger
(31) -> f(["apple","banana","pear"],["apple","banana","kiwi","apple"])
   (31)  0
RosLuP
fonte
2

C ++, 203 201 bytes

Obrigado ao @Quentin por salvar dois bytes!

#import<vector>
#import<string>
using T=std::vector<std::string>;
int f(T S,T L){for(int j,b,i=0;;++i)for(auto s:S){for(b=j=0;j<L.size();++j)if(L[j]==s){b=1;L.erase(begin(L)+j);break;}if(!b)return i;}}

Experimente online!

Steadybox
fonte
L.begin()-> begin(L)salva um byte :)
Quentin
Além disso, using T=std::vector<std::string>;salva outro! Quem sabia que a sintaxe bonita e moderna também poderia ajudar no golfe.
Quentin
@ Quentin Eu tentei isso no começo. Provavelmente houve algum erro de digitação simples que não notei.
Steadybox
1

PHP, 74 bytes

<?foreach($_GET[0]as$v)$t[]=array_count_values($_GET[1])[$v];echo+min($t);

Casos de teste

PHP, 108 bytes

<?[$x,$y]=$_GET;echo($a=array_intersect)($x,$y)==$x?min(($a._key)(array_count_values($y),array_flip($x))):0;

Casos de teste

Jörg Hülsermann
fonte
1

Pitão, 5 bytes

hS/LF

Leva a lista primeiro e o conjunto depois. Suíte de teste.

Explicação:

    F  Expand the input into l and s (not literally, 
                  since those are function names in Pyth, but...)
   L   for d in s:
  /        Count instances of d in l
   L   Package all the results as a list
 S     Sort the results smallest-first
h      grab the smallest element
Steven H.
fonte
1

C #, 36 bytes

f=(n,h)=>n.Min(c=>h.Count(x=>x==c));

ne hare string[]e a saída é um int.

Experimente online!

Essa resposta é inspirada na lógica de @ovs e @Alberto Rivera. Obrigado!

aloisdg movendo-se para codidact.com
fonte
1

Java, 135 bytes

int f(List<String> s,List<String> l){int n=0,i=0;while(i<s.size()){if(!l.remove(s.get(i++)))break;if(i==s.size()){n++;i=0;}};return n;}

Este é o meu primeiro desafio e resposta ao código de golfe, portanto, não tenho certeza sobre o formato. Precisa ser um programa de compilação completo? Preciso definir os parâmetros? Sugestões apreciadas.

EDIT : código agrupado em uma função. Obrigado @Steadybox

Hubert Grzeskowiak
fonte
Uma resposta pode ser um programa completo, uma função ou algum outro construto semelhante a uma função . Você pode usar os parâmetros, por exemplo, como argumentos para uma função ou a partir da entrada padrão.
precisa saber é o seguinte
1

05AB1E , 7 bytes

v²y¢})W

Experimente online!

v   }   # For each item in the first list...
 ²y¢    # Count the occurances in the second list.
     )W # Take the minimum occurrence count, return.
Urna de polvo mágico
fonte
1

Java, 114 bytes

<T>int a(Set<T>b,List<T>c){int m=2e32;b.stream().map(i->{int j=java.util.Collections.frequency(c,i);m=j<m?j:m;});return m;}

Tio em breve

Explicação

  • cria a variável local m.

  • mapeia o conjunto para um fluxo.

  • para cada elemento, se o número de ocorrências do elemento na lista for menor que m, m será definido para esse valor.

  • retorna m, que é o número de versões completas do conjunto

Targz
fonte
0

R 54 bytes

f<-function(s,l) min(table(factor(l[l%in%s],levels=s)))

Explicação: criando uma tabela das contagens apenas dos valores na lista que também aparecem na sublist.

Transformei a variável em um fator para gerar zeros se um valor que aparece na sub-lista não aparecer na lista. Finalmente, tomo o mínimo das contagens.

Michal
fonte
0

R, 61 57 44 bytes

print(min(sapply(s,function(x)sum(l%in%x))))

Função anônima. Aparentemente, você não precisa definir uma função para esse desafio. Economizou 13 bytes graças à contagem.

Explicação:

sum(l%in%x))retorna o número de vezes que uma string sé encontrada l.

lapply(s,function(x)) aplica isso a cada sequência s separadamente e retorna uma lista de somas.

min() retorna o menor da lista.

BLT
fonte
Pode ser reduzido para 40 bytes com um loop for:z=c();for(i in s)z[i]=sum(l%in%i);min(z)
count
Ou ainda mais para 37 bytes com sapply:min(sapply(s,function(x)sum(l%in%x)))
count
Brilhante, eu sempre esqueço que você pode somar booleanos. Vou editar isso mais tarde. Foi-me dito que preciso dessa impressão () se não for uma função.
BLT
0

JavaScript (ES6), 59 bytes

a=>b=>a.reduce((x,y)=>(l=b.filter(s=>s==y).length)>x?x:l)|0

Tente

f=

a=>b=>a.reduce((x,y)=>(l=b.filter(s=>s==y).length)>x?x:l)|0

console.log(f(["apple","banana"])(["apple","pear","apple","banana","banana"]))
console.log(f(["apple","banana"])(["apple", "pear", "apple", "banana", "apple"]))
console.log(f(["apple","banana","pear"])(["apple","banana","kiwi","apple"]))
console.log(f(["coconut"])([]))

Shaggy
fonte