Count occurences of a set in a list

Question

Given a non-empty set of strings and a list of strings, find out how many times the set occurs in the list, i.e. how many times you could create the set with items from the list. Every element from the list can only be used once.

Hint: a set is an unordered list of unique items.

Default input/output rules apply.

No external libraries allowed. Compiler/Interpreter standard libs are okay. This is code golf, so shortest solution counts.

---

Test cases:

["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: removed a sentence stating that the input params are defined in local scope. This contradicts the default IO rules linked above.

Answer 1

Python, 30 bytes

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

Try it online!

Answer 2

Jelly, 6 5 4 bytes

ċ@€Ṃ

Try it online!

The first argument of the program is the set, and the second argument is the list.

Explanation

ċ@€Ṃ
ċ@   -- 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 thanks to @ETHproductions

-1 byte again thanks to @ETHproductions

Answer 3

Jelly, 4 bytes

⁼þSṂ

Try it online!

How?

⁼þ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)

Answer 4

JavaScript (ES6), 56 bytes

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

Try it online

Answer 5

JavaScript (ES6), 64 bytes

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

Assumes both s and l are arrays of objects. Uses JavaScript strict equality for comparisons, so for instance [] === [] is false.

Answer 6

Haskell, 37 34 bytes

Thanks to @Laikoni for shaving off three bytes.

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

Call with (set::[a]) # (list::[a]) where a is any type deriving Eq.

Answer 7

CJam, 11 bytes

q~f{\e=}:e<

Try it online!

Explanation

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

Answer 8

Mathematica, 24 bytes

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

Pure function taking two lists as arguments in the suggested order and returning a nonnegative integer. Tally counts how many occurrences of every symbol occur in the input list, and #/.Rule@@@ converts each element of the input set into the corresponding number of occurrences.

Answer 9

T-SQL, 62 59 bytes

Previous version didn't work for sets with no matches

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

With s and l as tables and columns named the same as the table

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

Answer 10

Swift, 39 bytes

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

explanation:

s.map{} goes through each word in s and will produce an array of counts

w in names the mapped word for use in the next filter

l.filter{} aplies a filter to the l array

$0==w is the filter condition matching word w

.count gives the number of elements of l that met the condition

.min() returns the lowest count in the mapped result

Answer 11

APL (Dyalog), 9 bytes

⌊/+/⎕∘.≡⎕

Try it online!

⎕ get evaluated input (list of strings)

⎕∘.≡ get evaluated input (non-empty set of strings) and create equivalency table

+/ add across

⌊/ minimum across

Answer 12

C++, 203 201 bytes

Thanks to @Quentin for saving two 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;}}

Try it online!

Answer 13

Perl 6,  37  18 bytes

37

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

Try it

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 $_
}

See Sets, Bags, and Mixes for more information.

---

18

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

Try it

Explanation:

@^b.Bag create a Bag from the values
{@^a} key into that Bag (returns a list of counts)
.min get the minimum value of the resulting list

---

Answer 14

Axiom, 42 bytes

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

test code and results

(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

Answer 15

PHP, 74 Bytes

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

Testcases

PHP, 108 Bytes

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

Testcases

Answer 16

C#, 36 bytes

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

n and h are string[] and the output is an int.

Try it online!

This answer is inspire by @ovs and @Alberto Rivera's logic. Thank you!

Answer 17

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

This is my first code golf challenge and answer, so not sure about the format. Does it need to be a full compiling program? Do I need to define the parameters? Suggestions appreciated.

EDIT: wrapped code in a function. Thanks @Steadybox

Answer 18

Pyth, 5 bytes

hS/LF

Takes the list first and the set second. Test suite.

Explanation:

    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

Answer 19

05AB1E, 7 bytes

v²y¢})W

Try it online!

v   }   # For each item in the first list...
 ²y¢    # Count the occurances in the second list.
     )W # Take the minimum occurrence count, return.

Answer 20

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 coming soon

Explanation

• creates local variable m.

• maps the set to a stream.

• for each element, if the number of occurances of the element in the list is less than m, m is set to that value.

• returns m, which is the number of complete versions of the set

Answer 21

R, 61 57 44 bytes

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

Anonymous function. Apparently you don't have to define a function for this challenge. Saved 13 bytes thanks to count.

Explanation:

sum(l%in%x)) returns the number of times a string in s is found in l.

lapply(s,function(x)) applies that to each string in s separately and returns a list of sums.

min() returns the smallest from that list.

Answer 22

R 54 Bytes

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

Explanation: creating a table of the counts of only the values in the list that also appear in the sublist.

I then turn the variable into a factor in order to generate zeros if a value that appears in the sublist does not appear in the list. Finally, I take the minimum of the counts.

Answer 23

JavaScript (ES6), 59 bytes

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

---

Try it

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