5
$\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}}

$\endgroup$
  • $\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$ – user1066 Mar 5 '18 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$ – user42582 Mar 5 '18 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$ – user42582 Mar 5 '18 at 8:55
  • 1
    $\begingroup$ Can you give a sample input/output pair please? $\endgroup$ – Szabolcs Mar 5 '18 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$ – user1066 Mar 5 '18 at 10:20
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}} *)
$\endgroup$
  • 1
    $\begingroup$ This works, but if the multiset has a lot of dupes, too much is disposed of. $\endgroup$ – J. M. will be back soon Mar 5 '18 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$ – halirutan Mar 5 '18 at 12:24
  • $\begingroup$ @J.M. It works! $\endgroup$ – useranonis Mar 5 '18 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$ – J. M. will be back soon Mar 5 '18 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$ – useranonis Mar 6 '18 at 5:08
5
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.