Подсчет вхождений множества в список

15

Учитывая непустой набор строк и список строк, выясните, сколько раз набор встречается в списке, т. Е. Сколько раз вы могли создать набор с элементами из списка. Каждый элемент из списка может быть использован только один раз.

Подсказка: набор представляет собой неупорядоченный список уникальных предметов.

Применяются правила ввода / вывода по умолчанию .

Внешние библиотеки не допускаются. Стандартные библиотеки компилятора / интерпретатора в порядке. Это код гольф, поэтому самое короткое решение имеет значение.


Тестовые случаи:

["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

РЕДАКТИРОВАТЬ: удалено предложение о том, что входные параметры определены в локальной области видимости. Это противоречит правилам ввода-вывода по умолчанию, связанным выше.

Юбер Гжесковяк
источник
Да, это проясняет это. Однако я немного зациклен на третьем предложении. Что вы подразумеваете под "не обрабатывает объекты"?
Пост Рок Гарф Хантер
@WheatWizard некоторые языки не являются объектно-ориентированными и не знают концепции сравнения произвольных объектов.
Юбер Гжесковяк,
1
Вы, вероятно, должны изменить это на объектно-ориентированный, потому что каждый известный мне язык обрабатывает объекты какого-либо типа, даже если объекты являются закрытым классом. Я также должен отметить, что существует множество языков, которые вообще не могут обрабатывать строки.
Пост Рок Гарф Хантер
@WheatWizard хорошо, обновленное описание. Этот абзац предназначен для таких языков, как C, Assembler или Maple.
Юбер Гжесковяк,
Какие языки являются объектно-ориентированными? Что они должны использовать, если не строки? Я думаю, что проще всего было бы ограничиться только строками. Или, альтернативно, только целые числа. Посмотрите этот совет по использованию простейшего типа, которого достаточно.
xnor

Ответы:

12

Python, 30 байт

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

Попробуйте онлайн!

овс
источник
Хороший. Не думал об использовании карты. Вы можете сэкономить немного, используя печать вместо определения лямбда-BTW.
Юбер Гжесковяк,
1
@HubertGrzeskowiak Если изменить значение lambdaна a, printсчетчик байтов возрастет до 37 из-за двух input()требуемых значений .
Пост Рок Гарф Хантер
@WheatWizard, как указано в задании, рассмотрите входные данные, определенные в локальной области. Вы НЕ обязаны явно определять входные данные, например, в качестве параметров функции или пользовательских входов.
Юбер Гжесковяк,
@HubertGrzeskowiak если нет никаких оснований для этого, вы не должны переписывать свои значения по умолчанию для принятия ввода и вывода и наших значений по умолчанию для codegolf представлений
овс
@ovs О, я не знал об этом посте. Благодарю.
Юбер Гжесковяк,
6

Желе , 4 байта

⁼þSṂ

Попробуйте онлайн!

Как?

⁼þ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)
Джонатан Аллан
источник
6

Желе , 6 5 4 байта

ċ@€Ṃ

Попробуйте онлайн!

Первый аргумент программы - это набор, а второй аргумент - список.

объяснение

ċ@€Ṃ
ċ@   -- 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 байт благодаря @ETHproductions

-1 байт снова благодаря @ETHproductions

fireflame241
источник
Очень хорошо! Вы можете сохранить байт, объединив ссылки в одну строку: у ⁹ċ$€Ṃменя есть ощущение, что можно сделать короче, используя неявный правильный аргумент вместо ...
ETHproductions
Я думаю, что ċ@€Ṃ работает, чтобы сохранить еще один байт ... ( @переворачивает аргументы ċ)
ETHproductions
@ETHproductions работает правильно, насколько я тестировал.
fireflame241
Он не существовал до 12 мая прошлого года, но вместо @€(с обратными аргументами программе) сохраняет еще один байт: попробуйте онлайн!
Несвязанная Строка
6

JavaScript (ES6), 56 байт

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

Попробуйте онлайн

Альберто Ривера
источник
1
Сохраните 2 байта с помощью анонимной функции, а другую - с помощью параметров: n=>h=>Math.min(...n.map(c=>h.filter($=>$==c).length))для 53 байтов
Shaggy
5

JavaScript (ES6), 64 байта

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

Предполагает оба sи lявляются массивами объектов. Использует строгое равенство JavaScript для сравнений, например [] === [], false.

Нил
источник
Очень интересное решение. Пожалуйста, верните или распечатайте результат. AFAIK это возвращает анонимную функцию.
Юбер Гжесковяк,
2
@HubertGrzeskowiak Код, показанный на рисунке, является анонимной функцией. При вызове функция возвращает количество по желанию.
Нил
4

Haskell , 37 34 байта

Спасибо @Laikoni за то, что сбрил три байта.

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

Позвоните, (set::[a]) # (list::[a])где aпроисходит вывод любого типа Eq.

Юлианский волк
источник
Вместо length[y|y<-l,y==x]тебя можно использовать sum[1|y<-l,y==x].
Лайкони
@Laikoni, ты уверен в этом? Я думаю, что мне нужно было бы использовать что-то вроде этого sum[1|y<-l,y==x,_<-y], которое получается на два байта длиннее - хотя я определенно мог бы что-то там упустить
Джулиан Вольф
Неважно, ты определенно прав. Хороший звонок.
Джулиан Вольф
3

CJam , 11 байт

q~f{\e=}:e<

Попробуйте онлайн!

объяснение

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
Бизнес Кот
источник
3

Mathematica, 24 байта

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

Чистая функция, принимающая два списка в качестве аргументов в предложенном порядке и возвращающая неотрицательное целое число. Tallyподсчитывает, сколько вхождений каждого символа встречается во входном списке, и #/.Rule@@@преобразует каждый элемент входного набора в соответствующее число вхождений.

Грег Мартин
источник
3

T-SQL, 62 59 байт

Предыдущая версия не работала для наборов без совпадений

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

С s и l в качестве таблиц и столбцов, названных так же, как таблица

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
источник
3

Swift, 39 байт

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

объяснение:

s.map{} проходит через каждое слово в s и будет производить массив отсчетов

w in называет сопоставленное слово для использования в следующем фильтре

l.filter{} применяет фильтр к массиву l

$0==w соответствует ли условие фильтра слову w

.count дает количество элементов l, которые удовлетворяют условию

.min() возвращает наименьшее количество в сопоставленном результате

user68380
источник
1
Добро пожаловать в PPCG! Я добавил форматирование кода для вашего решения. Вы можете сделать это, добавив 4 пробела к строкам, которые содержат код.
Мего
3

APL (Дьялог) , 9 байт

⌊/+/⎕∘.≡⎕

Попробуйте онлайн!

 получить оцененный ввод (список строк)

⎕∘.≡ получить оцененный ввод (непустой набор строк) и создать таблицу эквивалентности

+/ добавить через

⌊/ минимум через

Адам
источник
2

Perl 6 ,  37  18 байт

37

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

Попытайся

Expanded:

{
  +( # 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 $_
}

Посмотрите Наборы, Мешки, и Смеси для получения дополнительной информации.


18

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

Попытайся

Объяснение:

@^b.Bagсоздать Bag из
{@^a}ключа значений в этот Bag (возвращает список отсчетов),
.minполучить минимальное значение результирующего списка


Брэд Гилберт b2gills
источник
Хорошие ответы, но ни одна из них не похожа на функции / полные программы
Джулиан Вольф
@JulianWolf У меня сложилось впечатление, что фрагменты были разрешены на основе утверждений «Считайте, что оба входа определены в текущей области видимости как s и l» и «Вам не нужно определять функцию». Я все равно пошел и отредактировал его ,
Брэд Гилберт b2gills
Ах, вы совершенно правы. Это, должно быть, было отредактировано в вопросе после того, как я прочитал это. В любом случае, мне нравится эстетика этой версии даже больше, чем предыдущая - синтаксис Perl всегда будет для меня загадкой.
Джулиан Вольф
@JulianWolf Это не очень хороший пример кода Perl 6. Я бы порекомендовал посмотреть 1-часовой доклад Овидия « Perl 6 - Почему люди так взволнованы» или посмотреть вкладку « Ресурсы » на Perl6.org .
Брэд Гилберт b2gills
Да, извините за путаницу. Это мой первый вызов, и я не знал, что уже есть правила для ввода и вывода. Я изменил его, потому что большинство ответов использовали эти правила, даже если это не требовалось.
Юбер Гжесковяк,
2

Аксиома, 42 байта

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

код теста и результаты

(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
источник
2

C ++, 203 201 байт

Спасибо @Quentin за сохранение двух байтов!

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

Попробуйте онлайн!

Steadybox
источник
L.begin()-> begin(L)сохраняет один байт :)
Квентин
Кроме того, using T=std::vector<std::string>;сохраняет другой! Кто знал, что современный красивый синтаксис также может помочь в игре в гольф.
Квентин,
@Quentin Я попробовал это сначала. Вероятно, была какая-то простая опечатка, которую я не заметил.
Steadybox
1

PHP, 74 байта

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

Testcases

PHP, 108 байт

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

Testcases

Йорг Хюльсерманн
источник
1

Pyth, 5 байт

hS/LF

Принимает список первым и набор вторым. Тестирование.

Объяснение:

    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
Стивен Х.
источник
1

C #, 36 байт

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

nи hесть string[]и выход int.

Попробуйте онлайн!

Этот ответ вдохновлен логикой @ovs и @Alberto Rivera. Спасибо!

aloisdg переходит на codidact.com
источник
1

Java, 135 байт

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

Это мой первый вызов и ответ по коду, поэтому не уверен насчет формата. Это должна быть программа полной компиляции? Нужно ли определять параметры? Предложения приветствуются.

РЕДАКТИРОВАТЬ : обернутый код в функции. Спасибо @Steadybox

Юбер Гжесковяк
источник
Ответом может быть полная программа, функция или некоторая другая функциональная конструкция . Вы можете взять параметры, например, в качестве аргументов функции или из стандартного ввода.
Steadybox
1

Java, 114 байт

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

Тио скоро

объяснение

  • создает локальную переменную m.

  • отображает набор в поток.

  • для каждого элемента, если число вхождений элемента в списке меньше, чем m, для m устанавливается это значение.

  • возвращает m, которое является числом полных версий набора

Targz
источник
0

R 54 байта

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

Объяснение: создание таблицы подсчетов только тех значений в списке, которые также отображаются в подсписке.

Затем я превращаю переменную в фактор, чтобы сгенерировать нули, если значение, которое появляется в подсписке, не появляется в списке. Наконец, я беру минимум из подсчета.

Michal
источник
0

R 61 57 44 байт

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

Анонимная функция. Очевидно, вам не нужно определять функцию для этой задачи. Сохранено 13 байт благодаря счетчику.

Объяснение:

sum(l%in%x))возвращает количество раз строки в sнайдена в l.

lapply(s,function(x))применяет это к каждой строке sотдельно и возвращает список сумм.

min() возвращает наименьшее из этого списка.

BLT
источник
Может быть уменьшен до 40 байт с помощью цикла for:z=c();for(i in s)z[i]=sum(l%in%i);min(z)
считать
Или еще дальше до 37 байтов с sapply:min(sapply(s,function(x)sum(l%in%x)))
считать
Бриллиант, я всегда забываю, что вы можете суммировать логические значения. Я отредактирую это позже. Мне сказали, что мне нужен этот print (), если это не функция.
BLT
0

JavaScript (ES6), 59 байт

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

Попытайся

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"])([]))

мохнатый
источник