Ask Your Question
1

Error in code or need more runtime?

asked 2015-01-04 12:16:02 -0500

mengen gravatar image

Hello everyone,

I would like to compute the number of sub-multisets (of a particular cardinality) of a multiset. The "mother" multiset contains exactly 2 copies of the numbers 0 through 52 (it has cardinality 106), and I would like to compute the number of distinct sub-multisets of size 14. I am attempting to do this with Sage (of course), and the code I am trying to use is as follows:

S = range(53); S.extend(range(53))

// This makes my mother set of two copies of the numbers 0 through 52

Hands = Subsets(S, 14, submultiset=true); Hands.cardinality()

// This defines a set of the sub-multisets of size 14, and then outputs their cardinality.

When I run this (in the Sage Notebook running inside Oracle VirtualBox with 2gb of allotted RAM), it gives me a small green rectangle that changes the cursor to a 'watch' as if it's still running. It's been like this for over and hour now. Is there an error in my code or should I expect such a calculation to take a 'long' time? I'm not familiar with 'large' calculations such as this one.

Thanks in advance!

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2015-01-05 06:12:54 -0500

Nathann gravatar image

You can kill the computation, for Sage is apparently trying to build all of these sets in order to count them. This is the default behaviour (and not always a very good idea) when no .cardinality() method has been implemented specifically for this problem.

Here, the number of submultiset of [0..52] containing at most twice the same element is at least the number of subsets of 53, i.e. at least 2^53. That is already too much.

If you know how this value should be computed, however, you are welcome to add this missing feature into Sage !

http://www.sagemath.org/doc/developer/

edit flag offensive delete link more
0

answered 2015-01-05 08:24:48 -0500

@Nathann's answer explains that with your code, Sage is not calculating the number but enumerating all submultisets, which in this case just takes too long.

For your particular counting problem, you can use compositions (also known as ordered partitions). You can iterate through compositions of 14 with maximum part 2, (there are 610 of them), and count each of them with an appropriate weight (some binomial coefficient) to account for the number of ways to choose which numbers the parts refer to.

sage: C = Compositions(14,outer=[2]*53) 
sage: C.cardinality()
610
sage: sum(binomial(53,len(c)) for c in C)
48204860086530
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-01-04 12:16:02 -0500

Seen: 63 times

Last updated: Jan 05 '15