# Subsets of a multiset

The function Subsets[] returns the subsets of a finite set of elements. This function has a shortcoming in that it treats repeated elements distinctively. Is there a function that returns the subset of a finite multiset of elements? That is, that unlike Subsets[] it treats repeated elements in-distinctively.

For example, if the new function is called NewSubsets, then the output should be:

NewSubsets[{a, b, c, c}]


{{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {c, c}, {a, b, c}, {a, c, c}, {b, c, c}, {a, b, c, c}}

• Is the expected output of newFn[{a,c,b,c}] {{}, {a}, {b}, {c, c}, {a, b}, {a, c, c}, {b, c, c}, {a, b, c, c}}, or something else? – user1066 Mar 5 '18 at 7:32
• I'm not sure if I understand the question, but I would suggest 1. exploring the second argument to Subsets and probably 2. looking at Tuples – user42582 Mar 5 '18 at 8:03
• perhaps you could provide an contained example of the output you'd expect to get from an input list eg {a,b,c}. – user42582 Mar 5 '18 at 8:55
• Can you give a sample input/output pair please? – Szabolcs Mar 5 '18 at 9:59
• I am sure I am missing something but why not DeleteDuplicates[Subsets[{a, c, b, c}]] (giving {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {c, c}, {a, b, c}, {a, c, c}, {b, c, c}, {a, b, c, c}})? As Szabolcs says, a sample input/output pair would help. – user1066 Mar 5 '18 at 10:20

I guess what you are after is

newSubsets[set_] := DeleteDuplicates[Subsets[set]];


It provides the result

newSubsets[{a, b, c, c}]
(* {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {c, c}, {a, b,
c}, {a, c, c}, {b, c, c}, {a, b, c, c}} *)

• This works, but if the multiset has a lot of dupes, too much is disposed of. – J. M. will be back soon Mar 5 '18 at 12:21
• And I see now, it was already posted in a hidden comment. Well, if push comes to shove, one could try to do it iteratively doing this for differently sized subsets one after another. – halirutan Mar 5 '18 at 12:24
• @J.M. It works! – useranonis Mar 5 '18 at 21:04
• @Richard, I don't doubt that it works, just that it is not combinatorially optimal when your multiset has many repeating elements. – J. M. will be back soon Mar 5 '18 at 23:18
• @J.M. I tested it to display the subsets of a chess (m-)set which has 7 different pieces, 5 of them repeated. The Length[] of it came out exactly. – useranonis Mar 6 '18 at 5:08

Here's a version based on Tuples that should be much faster if there are a lot of repeated elements:

Multisubsets[list_] := With[{c = Tally[list]},
Flatten /@ Tuples @ Replace[
c,
{k_, ct_} :> FoldList[Append, {}, Table[k, ct]],
{1}
]
]


res = Multisubsets[{a, b, c, c}]


{{}, {c}, {c, c}, {b}, {b, c}, {b, c, c}, {a}, {a, c}, {a, c, c}, {a, b}, {a, b, c}, {a, b, c, c}}

Check:

Sort @ res == DeleteDuplicates @ Subsets[{a, b, c, c}]


True

Timing test:

list = Join[Table[a, 20], Table[c, 3]];
r1 = DeleteDuplicates[Subsets[list]]; //AbsoluteTiming
r2 = Multisubsets[list]; //AbsoluteTiming

r1 == Sort[r2]


{8.36211, Null}

{0.000132, Null}

True

Almost 4 orders of magnitude faster.