Given a multiset (i.e., allow repeated elements), enumerate all distinct multi-subsets without using itertools(order is not important).

Example: Let s = 'a,a,b' then print to the console,


I am wondering if my approach (presented below) is efficient, and would appreciate stylistic advice. For example, I am not used to using *args, and in places my approach feels kludgey.

My attempt:

Count items in s:

A = s.split(',')
A_counts = defaultdict(int)
for i in A:
    A_counts[i] += 1

In our example we have {'a':2, 'b':1}. Use this to enumerate all tuples of points in the product of sets range(3)xrange(2), i.e., [[0,0],[0,1],[1,0],[1,1],[2,0],[2,1]]. Each tuple corresponds to a unique multi-subset. For example, the tuple [2,1] corresponds to a,a,b and the tuple [2,0] corresponds to a,a.

Enumerate all tuples:

def enumerate_tuples(*args):
    res = [[i] for i in range(args[0])]
    for arg in args[1:]:
        tmp = [j + [i] for i in range(arg) for j in res]
        res = tmp
    return res

Now print the corresponding multi-subset to console:

ordered_alphabet = list(A_counts)
args = (A_counts[i] + 1 for i in ordered_alphabet)
tuples = enumerate_tuples(*args)

# cycle through tuples printing corresponding string
for tup in tuples:
    if sum(tup) == 0: continue
    group = [ordered_alphabet[i] for i in range(len(tup)) for _ in range(tup[i])]
    out = ','.join(group)

2 Answers 2

  1. It's a good idea to divide code into functions — this makes it easier to document, test and reuse the code. Here it would make sense to have a function defined like this:

    def sub_multisets(elements):
        "Generate the sub-multisets of the iterable elements."
        # code goes here

    Then you could call sub_multisets(s.split(',')) or whatever in the main program.

  2. The code in the post omits one of the sub-multisets, namely the empty sub-multiset.

  3. Wherever you have code using defaultdict(int), consider using collections.Counter instead. This is a specialized data structure for counting things. Here you could write:

    A_counts = Counter(s.split(','))

    with no need for a loop.

  4. To compute the Cartesian product of some collections, use itertools.product. Here we need something like:

    product(*[range(n + 1) for n in A_count.values()])

    For example:

    >>> A_count = Counter('aab')
    >>> list(product(*[range(n + 1) for n in A_count.values()])
    [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]

    which are the sub-multiset counts required.

  5. To build the sub-multiset, we can use the Counter.elements method, for example if we have the counts (1, 1) we can write:

    >>> tuple(Counter(dict(zip(A_count.keys(), (1, 1)))).elements())
    ('a', 'b')

    Another way to do this would be to use itertools.repeat and itertools.chain:

    >>> tuple(chain.from_iterable(repeat(k, n) for k, n in zip(A_count.keys(), (2, 1))))
    ('a', 'a', 'b')

    but I think the Counter.elements approach is slightly simpler.

Putting all this together:

from collections import Counter
from itertools import product

def sub_multisets(elements):
    """Generate the sub-multisets of the iterable elements.
    For example:

    >>> [''.join(s) for s in sub_multisets('aab')]
    ['', 'b', 'a', 'ab', 'aa', 'aab']

    counts = Counter(elements)
    for sub_counts in product(*[range(n + 1) for n in counts.values()]):
        yield Counter(dict(zip(counts.keys(), sub_counts))).elements()
  • \$\begingroup\$ There is a requirement from OP to not use itertools. I agree knowing how to use itertools is good, but could you provide an alternative in each place you've used it? \$\endgroup\$
    – spyr03
    May 29, 2018 at 13:09
  • \$\begingroup\$ Not without knowing the reason for the requirement, no. (The itertools documentation has recipes which you could use instead of importing the corresponding function—look for the phrase "roughly equivalent to"—but why would you want to do that?) \$\endgroup\$ May 29, 2018 at 13:12
  • \$\begingroup\$ A learning experience? ("I want to write it myself", "My assignment says I can't use itertools") Writing code for a different implementation of python that maybe come with itertools out of the box? Those both seem like reasonable scenarios where you don't want an itertools solution. \$\endgroup\$
    – spyr03
    May 29, 2018 at 13:38
  • \$\begingroup\$ @spyr03: You might consider writing your own answer making those points. \$\endgroup\$ May 30, 2018 at 17:26
  1. A = s.split(',')
    A_counts = defaultdict(int)
    for i in A:
        A_counts[i] += 1

    You are basicly reinventing collections.Counter and this can be rewrote to

    counts = Counter(s.split(','))
  2. Why the string to tuple conversion?

    I am not sure why you are converting the input into tuples and then convert them back into strings corresponding the input again. Because you could have iterated over the a,a,b without the conversion

  3. Use libraries when possible

    I know you specifically said not to use itertools lib, but this seems the perfect spot to use it. If there is no specific reason for it (like an assignment) I recommend using it.

iterable = s.split(',')
multisets = set()
for r in range(1, len(iterable)+1):
    for comb in combinations(iterable, r):
        out = ','.join(comb)
        if out not in multisets:

Here is another approach, directly iterating over the string. And making combinations of them, lastly checking for distinct values by comparing to the multiset set

  • \$\begingroup\$ Regarding 2.: I'm not sure if I misunderstood what you mean, but iterating over the string 'a,a,b' would also include the commas and the item count would be 5, not 3. So it does make sense to use e.g. tuples as internal representation, and convert from/to strings for input and output. \$\endgroup\$
    – mkrieger1
    May 29, 2018 at 9:37
  • \$\begingroup\$ @mkrieger I meant iterating after the split happens, and making combinations of the list ['a', 'a', 'b'] \$\endgroup\$
    – Ludisposed
    May 29, 2018 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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