6
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Commented Mar 5, 2018 at 7:32
  • $\begingroup$ 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 $\endgroup$ Commented Mar 5, 2018 at 8:03
  • 1
    $\begingroup$ perhaps you could provide an contained example of the output you'd expect to get from an input list eg {a,b,c}. $\endgroup$ Commented Mar 5, 2018 at 8:55
  • 1
    $\begingroup$ Can you give a sample input/output pair please? $\endgroup$ Commented Mar 5, 2018 at 9:59
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 5, 2018 at 10:20

2 Answers 2

Reset to default
2
$\begingroup$

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}} *)
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This works, but if the multiset has a lot of dupes, too much is disposed of. $\endgroup$ Commented Mar 5, 2018 at 12:21
  • $\begingroup$ 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. $\endgroup$ Commented Mar 5, 2018 at 12:24
  • $\begingroup$ @J.M. It works! $\endgroup$ Commented Mar 5, 2018 at 21:04
  • 1
    $\begingroup$ @Richard, I don't doubt that it works, just that it is not combinatorially optimal when your multiset has many repeating elements. $\endgroup$ Commented Mar 5, 2018 at 23:18
  • $\begingroup$ @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. $\endgroup$ Commented Mar 6, 2018 at 5:08
7
$\begingroup$

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

For your example:

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.