Implement bag operations

Question

A bag, also called a multiset, is an unordered collection. You can call it a set that allows duplicates, or a list (or an array) that is not ordered/indexed. In this challenge, you are asked to implement bag operations: addition, difference, multiplication, division, counting and equality test.

Operations

The specified operations may not be conventional.

• addition combines two bags into one, conserving the total number of each value
  [1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
• difference removes from a bag each element of another bag, or does nothing if no such element
  [1,2,2,4] - [1,2] = [2,4] [1,2,3] - [2,4] = [1,3]
• multiplication multiplies each element in the bag.
  [1,2,3,3,4] * 3 = [1,1,1,2,2,2,3,3,3,3,3,3,4,4,4] 2 * [1,3] = [1,1,3,3]
• division is an uncommon one: each n equal elements are put in n equal new bags, elements that cannot form an n-group remain in the bag. Return any one of the n new bags.
  [1,1,2,2,2] / 2 = [1,2] [1,2,2,3,3,3] / 3 = [3]
• counting counts how many divisor bags can be produced from the dividend bag
  [1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
• equality test checks if two bags have the same numbers of each element
  [1,2,2,3] == [3,2,1,2] = truthy [1,2,3] == [1,2,2,3] = falsy (can also use = for this)

If you are using your own symbols for the operators, please specify.

Formats

Bags will be displayed as lists of the form [1,1,2,3,4]. You can use any other bracket than square ones, or even use quotes, or nothing at all. The elements will be integers(mathematically, not necessarily int) for the purpose of this question. Bags do not have to be sorted.

The input format will be two bags or a bag and an integer, with an operator. You can specify your own format as long as it contains these three.

The output format should be a single bag of the same format.

Rules

• you may not use built-in functions, operations or libraries (including the standard library) that already implement these; it's ok though to use list concatenation and multiplication since they are by definition list operations, not bag operations (which happen to basically do the same thing)
• standard loopholes apply
• shortest answer wins

Test cases

[1,2,2,3] + [1,2,4]
[1,1,2,2,2,3,4]

[1,2,2,4] - [1,2]
[2,4]

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

[1,2,3,3,4] * 3
[1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]

2 * [1,3]
[1,1,3,3]

[1,1,2,2,2] / 2
[1,2]

[1,2,2,3,3,3] / 3
[3]

[1,1,2,2,2,2,3,3,3] c [1,2,3]
2

[3,2,1,2] == [1,2,2,3]
truthy

[1,2,3] == [1,2,2,3]
falsy

Answer 1

APL (155)

∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕

This defines an operator ∆ 'bag', which defines bag operations for given functions. I.e. +∆ would be addition. It then reads a line from the keyboard and evaluates it as an APL expression.

The functions are:

• +∆, addition
• -∆, subtraction
• ×∆, multiplication
• ÷∆, division
• ⊂∆, counting
• ≡∆, equivalence (though due to golfing any unrecognized function will do equivalence)

Explanation:

• ∆←{...}: define an operator ∆:

  • O←⍺⍺: store the given function in O (⎕CR won't work with ⍺⍺ directly)
  • O←⎕CR'O': get the string representation of that function
  • '+'=O...:: for addition,
    • ⍺,⍵: join the two lists together
    • R[⍋R←...]: and sort the result
  • '-'=O:: for subtraction,
    • ⍺{...}⍵: run the following recursive function:
      • ⍵≡⍬:⍺: if the subtrahend is empty, return the minuend
      • ⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: otherwise, remove the first element of the subtrahend from both the subtrahend and the minuend and try again
  • (⍬=⍴⍵)∧K←'×'=O: for multiplication, and if the right argument is not a bag:
    • ⍵/⍺: replicate each element in the left argument by the right argument
  • K:: ...and if the right argument is a bag:
    • ⍺/⍵: replicate each element in the right argument by the left argument (this is so that multiplication is commutative)
  • '÷'=O:: for division,
    • ⍵≤⍺∘.+⍺: see which elements in ⍺ occur at least ⍵ times,
    • ⍺/⍨: select those from ⍺,
    • ∪: and remove all duplicates from that list
  • '⊂'=O:: for counting,
    • ⍵{...}⍺: run the following recursive function:
      • (∪⍺)≢∪⍵:0: if one list contains elements the other doesn't, the result is 0
      • 1+⍺∇⍵-∆⍺: otherwise, subtract the dividend from the divisor, try again, and increment the result.
  • ⋄: if none of the above, do the equivalence test:
    • ⍺[⍋⍺]≡⍵[⍋⍵]: sort both lists and see if they are equal

• ⎕: read an expression from the keyboard, evaluate it, and output the result.

Test cases:

      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 +∆ 1 2 4
1 1 2 2 2 3 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 4 -∆ 1 2
2 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 -∆ 2 4
1 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 3 4 ×∆ 3
1 1 1 2 2 2 3 3 3 3 3 3 4 4 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      2 ×∆ 1 3
1 1 3 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 ÷∆ 2
1 2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 3 3 ÷∆ 3
3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 2 3 3 3 ⊂∆ 1 2 3
2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      3 2 1 2 ≡∆ 1 2 2 3
1
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 ≡∆ 1 2 2 3
0

Answer 2

JavaScript (ES6), 260 bytes

(x,o,y,a=a=>a.reduce((r,e,i)=>[...r,...Array(e).fill(i)],[]),b=(a,r=[])=>a.map(e=>r[e]=-~r[e])&&r)=>[z=>a(b(y,z)),z=>y.map(e=>z[e]&&z[e]--)&&a(z),z=>a(z.map(e=>e*y)),z=>a(z.map(i=>i/y|0)),z=>b(y).map((e,i)=>r=Math.min(r,z[i]/e),r=1/0)|r,z=>``+z==b(y)][o](b(x))

Takes 3 parameters. The first parameter is an array, the second is an operator, the third depends on the operator. Bags are required to hold non-negative integers.

[...] 0 [...] -> addition
[...] 1 [...] -> difference
[...] 2 <n> -> multiplication
[...] 3 <n> -> division
[...] 4 [...] -> counting
[...] 5 [...] -> equality

Ungolfed:

function do_bag_op(lhs, op, rhs) {
    function bag2array(bag) {
        return bag.reduce(function (result, entry, index) {
            return result.concat(Array(entry).fill(index));
        }, []);
    }
    function array2bag(array, bag) {
        if (!bag) bag = [];
        array.forEach(function (entry) {
            if (bag[entry]) bag[entry]++;
            else bag[entry] = 1;
        }
        return bag;
    }
    var bag = array2bag(lhs);
    switch (o) {
    case 0: // addition
        return bag2array(array2bag(rhs, bag));
    case 1: // difference
        rhs.forEach(function(entry) {
            if (bag[entry]) bag[entry]--;
        });
        return bag2array(bag);
    case 2: // multiplication
        return bag2array(bag.map(function (entry) {
            return entry * rhs;
        }));
    case 3: // division
        return bag2array(bag.map(function (entry) {
            return Math.floor(entry / rhs);
        }));
    case 4: // counting
        return Math.floor(array2bag(rhs).reduce(function (count, entry, index) {
            return Math.min(count, bag[index] / entry);
        }, Infinity));
    case 5: // equality
        return String(bag) == String(array2bag(rhs));
    }
}

Answer 3

Octave, 253 244 226 bytes

function r=f(a,b,o)
u=union(a,b);p=hist(a,u);q=hist(b,u);m=d=0;if(numel(b)==1)m=p.*b;d=p/b;elseif(numel(a)==1)m=a.*q;end
r={p+q,p-q,m,d,min(fix(p./q)),isequal(p,q)}{o};if(o<5)r=[arrayfun(@(x,y)repmat(y,1,x),r,u,'un',0){:}];end

This function must be in a file. To write the function in the command window you must use endfunction or end.

Thanks to Luis Mendo for saving 18 bytes.

The operations are:

1 = addition
2 = difference
3 = multiplication
4 = division
5 = counting
6 = equality test

Usage example:

>> f([1,2,2,3], [1,2,4], 1)
ans = 1   1   2   2   2   3   4

>> f([1,2,2,4], [1,2], 2)
ans = 2   4

>> f([1,2,3], [2,4], 2)
ans = 1   3

>> f([1,2,3,3,4], 3, 3)
ans = 1   1   1   2   2   2   3   3   3   3   3   3   4   4   4

>> f(2, [1,3], 3)
ans = 1   1   3   3

>> f([1,1,2,2,2], 2, 4)
ans = 1   2

>> f([1,2,2,3,3,3], 3, 4)
ans =  3

>> f([1,1,2,2,2,2,3,3,3], [1,2,3], 5)
ans =  2

>> f([3,2,1,2], [1,2,2,3], 6)
ans =  1

>> f([1,2,3], [1,2,2,3], 6)
ans = 0

Ungolfed:

function r = f(a,b,o)
    u = union(a,b);
    p = hist(a,u);
    q = hist(b,u);
    m = d = 0;
    if (numel(b)==1)
        m = p.*b;
        d = p/b;
    elseif (numel(a)==1) 
        m = a.*q;
    end
    r = {p+q, p-q, m, d, min(fix(p./q)), isequal(p,q)}{o};
    if (o<5)
        r = [arrayfun(@(x,y) repmat(y, 1, x), r, u, 'un', 0){:}];
    end
end

Answer 4

Mathematica, 387 347 300 284 bytes

k=KeyValueMap[Table,#]&;j=b@@Join@@#&;l=List;q=Counts
b~SetAttributes~Orderless
a_b+c_b^:=j@{a,c}
c_b-a_b^:=j@k@Merge[q/@(l@@@{a+c,2a}),-Min[0,+##2-#]&@@#&]
a_b*n_Integer/;n>0^:=a+a*(n-1)
a_Rational c_b^:=j@k[⌊a#⌋&/@q@*l@@c]
a_b==d_b^:=l@@a==l@@d
c_b/a_b^:=If[(c-a)+a==c,1+(c-a)/a,0]

Slightly degolfed (a.k.a old version), didn't have full support for equality tests (returned truthy values, but left unevaluated for non-matching bags).

SetAttributes[b,Orderless]
b/:-a_b:=d@@a
b/:a_b+c_b:=Join[a,c]
d/:a_b+c_d:=b@@Join@@KeyValueMap[Table,Merge[Counts/@(List@@@{a+b@@c,b@@c+b@@c}),Max[0,#-(+##2)]&@@#&]]
b/:Rational[1,a_]c_b:=b@@Join@@KeyValueMap[Table,Floor[#/a]&/@Counts@*List@@c]
b/:(a_b)^-1:=c@@a
c/:a_b d_c:=Min@Merge[Counts/@(List@@@{a,d}),If[+##2==0,\[Infinity],#/+##2]&@@#&]
b/:a_b*n_Integer:=a+a*(n-1)

Implements the required data type with head b.

First b is defined to be Orderless. Any object passed to the kernel with head b will autosort its arguments. So even if b[3,2,1] is typed in, the evaluator will never see anything other than b[1,2,3].

Addition is trivially defined as joining the elements.

A special rule for the difference of two bags is defined (explained below). Previous version had an auxiliary symbol for expressions of form -bag.

Then multiplication (as long as n is a positive integer) is recursively defined as n*b[...] = b[...] + (n-1)*b[...] which will eventually reduce to a simple sum.

The special rule for b[...] - b[...] counts the number of distinct elements in the sum of the bags and subtracts the bag to be subtracted twice from that result. Easier explained:

b[1,2,3,4,5] - b[2,3,6]
Element counts in sum of bags: <|1->1, 2->2, 3->2, 4->1, 5->1, 6->1|>
Element counts in 2x second bag:     <|2->2, 3->2, 6->2|>
Subtracting the corresponding values:
                               <|1->1, 2->0, 3->0, 4->1, 5->1, 6->-1|>

Above is a list of Keys->Values. KeyValueMap with Table creates lists of each Key Value times. (there's also a Max[...,0] there to not attempt creation of negative length tables). This comes out as:

{{1},{},{},{4},{5},{}}

which is flattened and head List is replaced with b.

Division by integers is somewhat similar in functions used, it is simply the floored division of the element counts by the integer.

Division by sets or counting I've changed since the original implementation. It is now recursively done as follows. Say, we divide bag b1 by b2 (which in the golfed code are c and a respectively. If (b1-b2) + b2 == b1, then add 1 and add to that the result of dividing (b1-b2)/b2. If not, return 0 and exit the recursion.

If bags match, built-in == gives True. The last line forces a False if they don't.

Test cases:

Input:
b[1, 2, 2, 3] + b[1, 2, 4]
b[1, 2, 2, 4] - b[1, 2]
b[1, 2, 3] - b[2, 4]
b[1, 2, 3, 3, 4]*3
2*b[1, 3]
b[1, 1, 2, 2, 2]/2
b[1, 2, 2, 3, 3, 3]/3
b[1, 1, 2, 2, 2, 2, 3, 3, 3] /b[1, 2, 3]
b[3, 2, 1, 2] == b[1, 2, 2, 3]
b[1, 2, 3] == b[1, 2, 2, 3]

Output:
b[1, 1, 2, 2, 2, 3, 4]
b[2, 4]
b[1, 3]
b[1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4]
b[1, 1, 3, 3]
b[1, 2]
b[3]
2
True
False

Answer 5

05AB1E, 92 87 83 82 77 bytes

>i‚˜,}¹iи˜Qis}GD})˜,}¹<i³v²y¢O}){0è,}¹Íi{s{Q,}¹Í<iÙv²y¢O³‹_iy}}),}svy†¬yQi¦}}

Split by operation

>i                      # if 0
  ‚˜,}                  # addition
¹i                      # if 1
  и˜Qis}GD})˜,}        # multiplication
¹<i                     # if 2
   ³v²y¢O}){0è,}        # count
¹Íi                     # if 3
   {s{Q,}               # equality
¹Í<i                    # if 4
   Ùv²y¢O³÷Fy}}),}      # division
                        # else
   svy†¬yQi¦}}          # difference

Explanation

Addition

‚˜,}

Put one bag in other and flatten them to one bag.

Multiplication

и˜Qis}

Make sure the number is on the top of the stack. Call this X.

GD})˜,}

Duplicate the bag X times and join to one bag.

Count

³v²y¢O}){0è,}

For each element in the divisor bag, count number of occurences in dividend bag.
The minimum count will be the number of bags we can make.

Equality

 {s{Q,}

Sort both bags and check if they're equal.

Division

Ùv²y¢O³÷Fy}}),}

Count how many times each unique element occurs in the bag.
If it occurs at least as many times as the divisor. Keep (nr_of_copies_total // divisor) copies in the bag.

Difference

svy†¬yQi¦}} 

For each element in the subtrahend, sort it to the front of the minuend.
If the current subtrahend if equal to the first element in the minuend, remove it from the minuend.

Answer 6

Q - 219 characters

a:(,)
s:{[x;y]x((!:)(#:)x)except(,/)({.[(#);x]}')flip(7h$(({(+/)x=y}[y]')(?:)y);(({where x=y}[x]')y))}
m:{(,/)$[0>(@:)x;(#[x]')y;(#[y]')x]}
d:{(?:)x(&:)({y<=(+/)x=z}[x;y]')x}
c:{min({(+/)x=y}[x]')y}
e:{(asc x)~asc y}

a for addition, s for difference (subtraction), m for multiplication, d for division, c for counting, e for equality.

The addition algorithm is the obvious one, just joining the bags.

The subtraction function indexes in input bag (represented as an array) with the entire index range, except for the first n indices of each equivalence class formed by equality to each element in y, where n is the number of copies of that representative in y. Handling possible duplicates in y makes this a real monster of a function.

The multiplication function takes x values from each y, in the case that y is a single value, instead of an array, it just replicates them.

The division function produces the values whose count in the array is greater than y, and then removes duplicates.

The counting function calculates the counts of each element in y, and then returns the minimum.

Two bags are equal if their sorted array representations are equal.

Answer 7

Ruby, class definition answer, 323 291 bytes

Mostly just wanted to make the Bag an actual class because of Ruby's flexibility with classes. In this case, it inherits from Array because it's shorter than having to initialize an internal array and dealing with the other stuff.

I'll probably do a more-serious golfing answer that uses a function to deal with the operations tomorrow. I'm very tired and I had too much fun with this even though I had to wrangle with the numerics class definition to get Number * Bag working properly PRAISE THE COERCE FUNCTION FOR MAKING IT SO I DIDN'T NEED TO MESS UP THE NUMERICS CLASS DEFINITIONS

Try it online! (Whitespace doesn't matter in Ruby, so the code is slightly ungolfed there.)

class B<Array
def == o
sort==o.sort
end
def + o
B.new super
end
def - o
r=to_a
o.map{|i|r[r.index(i)||size]=p}
B.new r-[p]
end
def * i
B.new super
end
def / i
B.new uniq.map{|o|[o]*(count(o)/i)}.flatten
end
def c o
o.map{|i|count i}.min
end
def inspect
sort
end
def coerce o
[self,o]
end
end

Answer 8

Ruby, 201 bytes

As promised in my other answer, here's one that uses functions instead of building a new class. I'm so close to breaching the 200 byte mark... Try it online

This uses the same opcodes as @Neil in his JavaScript answer, and the same order of arguments (lhs, opcode, rhs)

0: Addition
1: Difference
2: Multiplication
3: Division
4: Counting
5: Equality

---

The code:

->x,o,y{[->{(x+y).sort},->r=[*x]{y.map{|i|r[r.index(i)||x.size]=p};r-[p]},->{(x==[*x]?x*y :y*x).sort},->{x.uniq.map{|i|[i]*(x.count(i)/y)}.flatten},->{y.map{|i|x.count i}.min},->{x.sort==y.sort}][o][]}

Answer 9

C++, 555 551 bytes

(line breaks added for readability - only the first newline is required and counted)

#include<map>
struct B:std::map<int,int>{
B(std::initializer_list<int>l){for(auto i:l)++(*this)[i];}};
B operator+(B a,B b){for(auto m:b)a[m.first]+=m.second;return a;}
B operator-(B a,B b){for(auto m:b){int&x=a[m.first];x-=x>m.second?m.second:x;if(!x)a.erase(m.first);};return a;}
B operator*(B b,int n){for(auto m:b)b[m.first]*=n;return b;}
B operator*(int n,B b){return b*n;}
B operator/(B b,int n){for(auto m:b)if(!(b[m.first]/=n))b.erase(m.first);return b;}
int operator/(B a,B b){auto r=~0u;for(auto m:b){int x=a[m.first]/m.second;r=r>x?x:r;}return r;}

Explanation

We implement our bag as a map of (value, count). The basic operations can be implemented by manipulating the counts; subtraction and integer division also need to remove any elements whose count reaches zero, so that std::map::operator== will work as the equality test.

The following expanded code is a generic version of the above, much less golfed: we use a separate s() to squeeze out any zero-count values, and we implement const operations in terms of assignment operators in the idiomatic C++ way. We also use s() to make multiplication by 0 return a truly empty bag (tested by adding (B{1}*0 != B{}) to main()); the original fails this test, and it's not clear whether it's a requirement.

template<class T>
struct Bag{
    std::map<T,int>b;
    Bag(const std::initializer_list<T>& l){for(auto i:l)++b[i];}
    Bag&s(){for(auto i=b.begin();i!=b.end();i=i->second?++i:b.erase(i));return*this;}
    Bag&operator+=(const Bag& o){for(auto m:o.b)b[m.first]+=m.second;return*this;}
    Bag&operator-=(const Bag& o){for(auto m:o.b){auto&x=b[m.first];x-=x>m.second?m.second:x;}return s();}
    Bag&operator*=(int n){for(auto m:b)b[m.first]*=n;return s();}
    Bag&operator/=(int n){for(auto m:b)b[m.first]/=n;return s();}
    auto operator/=(const Bag& o){auto r=~0u;for(auto m:o.b){int x=b[m.first]/m.second;r=r>x?x:r;}return r;}
    bool operator==(const Bag& o)const{return b==o.b;}

    Bag operator+(Bag o)const{return o+=*this;}
    Bag operator-(const Bag& o)const{Bag t=*this;return t-=o;}
    Bag operator*(int n)const{Bag t=*this;return t*=n;}
    friend Bag operator*(int n,const Bag& b){return b*n;}
    auto operator/(auto n)const{Bag t=*this;return t/=n;}
    bool operator!=(const Bag& o)const{return b!=o.b;}
};

using B = Bag<int>;

Tests

bool operator!=(B a,B b){return!(a==b);}
int main()
{
    return 0
        + (B{1,2,2,3}+B{1,2,4}  !=  B{1,1,2,2,2,3,4})
        + (B{1,2,2,4}-B{1,2}  !=  B{2,4})
        + (B{1,2,3}-B{2,4}  !=  B{1,3})
        + (B{1,2,3,3,4}*3  !=  B{1,1,1,2,2,2,3,3,3,3,3,3,4,4,4})
        + (2*B{1,3}  !=  B{1,1,3,3})
        + (B{1,1,2,2,2}/2  !=  B{1,2})
        + (B{1,2,2,3,3,3}/3  !=  B{3})
        + (B{1,1,2,2,2,2,3,3,3}/B{1,2,3} != 2)
        + (B{3,2,1,2}  !=  B{1,2,2,3})
        + (B{1,2,3}  ==  B{1,2,2,3})
        ;
}

Answer 10

Python 2.7 - 447B (filesize)

This is my first try at Codegolf, I hope it satisfies. I needed 2h. (But I'm still a beginner at Python)

Edit: Thanks to "Kevin Lau - not Kenny" for pointing out these:

• pythons self argument in a class can be replaced by anything
• indentation only has to be a single space
• the builtin sorted - funktion (I knew I had seen it, but I thought it to be a method in lists)
• __ radd __ is not needed (I only support adding B-objects(Bag-type) anyways)

Edit: Additionally I saved space by replacing functions with lambdas and new lines and indentations with more semicolons.

Code:

class B:
 def __init__(S,L=[]):S.L=sorted(list(L));S.p=lambda:[[i]*S.L.count(i)for k,i in enumerate(S.L)if i!=S.L[k-1]];S.__eq__=lambda o:S.L==o.L;S.__rmul__=S.__mul__=lambda o:B(S.L*o);S.__add__=lambda o:B(S.L+o.L);S.__sub__=lambda o:B([i for k in S.p()for i in k[:max(0,S.L.count(k[0])-o.L.count(k[0]))]]);S.__div__=lambda o:B([i for k in S.p()for i in k[::o][:[-1,None][len(k)%o==0]]]);S.c=lambda o:min([S.L.count(i)//o.L.count(i)for i in o.L])

checks:

print B([1,2,2,3]) + B([1,2,4]) == B([1,1,2,2,2,3,4]) # Add

print B([1,2,2,4]) - B([1,2]) == B([2,4]) #Substract
print B([1,2,3])   - B([2,4]) == B([1,3]) #Substract

print B([1,2,3,3,4]) * 3 == B([1,1,1,2,2,2,3,3,3,3,3,3,4,4,4])#Multiply
print 2 * B([1,3]) == B([1,1,3,3])                            #

print B([1,1,2,2,2])   /2 == B([1,2]) #Divide
print B([1,2,2,3,3,3]) /3 == B([3])   #

print B([1,1,2,2,2,2,3,3,3]).c(B([1,2,3]))==2 #Contained n times

print B([3,2,1,2]) == B([1,2,2,3]) # Equal
print B([1,2,3])   == B([1,2,2,3]) # Unequal

Output:

True
True
True
True
True
True
True
True
True
False

I might try it an other time with set as basis some time. Edit: Maybe I'll even try with functions only.

Answer 11

Go, 642 bytes

type B struct{C map[int]int}
func N(c...int)B{b:=B{make(map[int]int)};for _,d:=range c{b.C[d]+=1};return b}
func(b B)L()(o[]int){for k,v:=range b.C{for i:=0;i<v;i++{o=append(o,k)}};return}
func(b*B)A(O B)B{for k,v:=range O.C{b.C[k]+=v};return*b}
func(b*B)S(O B)B{for k,v:=range O.C{if _,o:=b.C[k];o{b.C[k]-=v}};return*b}
func(b*B)M(n int)B{for k:=range b.C{b.C[k]*=n};return*b}
func(b*B)D(n int)B{for k:=range b.C{b.C[k]/=n;if b.C[k]==0{delete(b.C,k)}};return*b}
func(b B)O(O B)int{i:=0;for;len(b.L())>len(O.L());i++{b=b.S(O)};return i}
func(b B)E(O B)bool{for k,v:=range b.C{if V,o:=O.C[k];o{if V!=v{return 0>1}}else{return 0>1}};return 0<1}

Attempt This Online!

Methods ASMDOE are the methods described in-order in the OP. N is the constructor, taking a list of ints, and L is a utility function that turns a bag into a list of ints.

Go, generic, 712 bytes

type B[T comparable]struct{C map[T]int}
func N[T comparable](c...T)B[T]{b:=B[T]{make(map[T]int)};for _,d:=range c{b.C[d]+=1};return b}
func(b B[T])L()(o[]T){for k,v:=range b.C{for i:=0;i<v;i++{o=append(o,k)}};return}
func(b*B[T])A(O B[T])B[T]{for k,v:=range O.C{b.C[k]+=v};return*b}
func(b*B[T])S(O B[T])B[T]{for k,v:=range O.C{if _,o:=b.C[k];o{b.C[k]-=v}};return*b}
func(b*B[T])M(n int)B[T]{for k:=range b.C{b.C[k]*=n};return*b}
func(b*B[T])D(n int)B[T]{for k:=range b.C{b.C[k]/=n;if b.C[k]==0{delete(b.C,k)}};return*b}
func(b B[T])O(O B[T])int{i:=0;for;len(b.L())>len(O.L());i++{b=b.S(O)};return i}
func(b B[T])E(O B[T])bool{for k,v:=range b.C{if V,o:=O.C[k];o{if V!=v{return 0>1}}else{return 0>1}};return 0<1}

Attempt This Online!