4
\$\begingroup\$

This is a simple multiset coefficient calculator in python, that will calculate both standard multiset coefficients, as well as multiset coefficients with repetition limits, used initially as part of a dice pool probability calculation program.

I primarily want to see if there's any way to improve the general case algorithm - it pretty faithfully reproduces the mathematical formula for repetition-limited multiset coefficients, but I'm not certain if such a faithful reproduction is necessarily the fastest or most computationally efficient form (although it certainly should be readable).

Further, are there any obvious special cases that I've missed? My own investigations show that these should just be the 4 special cases that reduce down to simpler forms, but I can't claim I've definitively proved that.

from math import comb

def multichoose(n, k, r=None):
    """ Return the number of multisets (aka combinations with replacement) of 
        length k using n symbols, with a limit of r repetitions of any given symbol. 
        Where limit is not given, returns the number of multisets with no repetition limit.
        multichoose will accept floats, but will truncate them to ints before use.
    """ 
    #Check input is numeric by passing through int()
    try:
        symbols = int(n)
        length = int(k)
        limit = int(r)
    except TypeError:
        print("TypeError: Parameters must be numeric")
        raise
    else:
        raise
    
    #Check parameters are non-negative
    if symbols < 0 or length < 0 or limit < 0:
        raise ValueError("Parameters cannot be negative")
    
    
    #Special cases: Note that the order of these elifs is significant - Empty set case 
    #is more general than no limit case, which is more general than the value limit cases.
    
    #Empty set case: by definition, multichoose(n,0) == 1, so we can save time by separating 
    #out this case. Further, it allows us to avoid an error for multichoose(0,0), since the
    #formula will equate to comb(-1,0), which would otherwise throw an error.
    elif length == 0:
        return 1 
        
    #No limit case: n multichoose k no limit is a simple combinatorial, so we can again 
    #save time by pulling out that special case. Further, if r >= k, the algorithm will 
    #return the same answer as if there was no limit, so let's add that special case to 
    #this one.
    elif limit is None or limit >= length:
        return comb(symbols + length - 1, length)
        
    #Limit 0 case: if k > 0, You can't make a multiset if you're not allowed to choose a 
    #symbol. Our general case algorithm will return the right answer, but will take the 
    #longest possible route to get there, so better to save time by pulling out the special
    #case.
    elif limit == 0:
        return 0
        
    #Limit 1 case: reduces to n choose k. Again, our general case algorithm will return 
    #the right answer, but will take the longest possible route to get there, so again we 
    #can save time by pulling out that special case.
    elif limit == 1:
        return comb(symbols, length)
        
        
    #General case: uses an include-exclude algorithm to calculate the limited multi-choose.
    #As the algorithm itself uses an unlimited multichoose function, we can  
    #recursively call our no-limit case to calculate that function, simplifying the code. 
    else:
        result = 0
        for i in range(0,min(symbols,length // (limit + 1)) + 1 ):
            result += (-1)**i * comb(symbols, i) * multichoose(symbols, length - i*(limit + 1))
        return result
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

cite your reference

it pretty faithfully reproduces the mathematical formula

Tell us about the formula, perhaps with an URL. Mention it as a comment in the source code. Then we could reason about how closely the code matches the cited reference.

spurious kwarg

I don't understand what's going on here:

def multichoose(n, k, r=None):
        ...
        limit = int(r)

If we defaulted r to e.g. 1, that would make sense. But to invite caller to let it default, and then raise fatal TypeError, just seems cruel.

And it looks like you don't need the try .. else: clause.

    elif limit is None or limit >= length:

I similarly don't understand this line. Didn't we just blow up when evaluating int(None) ? Isn't this equivalent to elif False or ... ? Better to simplify by eliding the first disjunct.

helpful comments

Thank you for the discussion of the various cases. It sheds much light on the problem.

I feel the various elifs would be more clearly stated as if .. return .... There's no need for the Gentle Reader to maintain context across all that discussion.

code coverage

I recommend you use pytest --cov --cov-report=term-missing *.py to verify that your test suite exercises each of the special cases, and obtains a correct answer. Of course, that implies adding an automated test suite to this submission.

Having done that, you might temporarily omit the special cases and verify that the general code eventually produces the same answer. Comparative timings would also be of interest.

\$\endgroup\$
1
  • \$\begingroup\$ You are quite correct on r/limit note - that's an error that somehow got through my very manual tests and I'm glad has been caught, appreciate the review. There should be a test for r = None first before passing through int. As for reference, apologies, this would be the formula I'm basing this on: math.stackexchange.com/questions/98065/…. Again, I'll make sure to add that to the comments in my version of the code. \$\endgroup\$ Apr 3 at 4:00

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.