class_docstr: Has methods to ``enumerate`` and ``count`` the partitions of a multiset.
  
  This implements a refactored and extended version of Knuth's algorithm
  7.1.2.5M [AOCP]_."
  
  The enumeration methods of this class are generators and return
  data structures which can be interpreted by the same visitor
  functions used for the output of ``multiset_partitions_taocp``.
  
  Examples
  ========
  
  >>> from sympy.utilities.enumerative import MultisetPartitionTraverser
  >>> m = MultisetPartitionTraverser()
  >>> m.count_partitions([4,4,4,2])
  127750
  >>> m.count_partitions([3,3,3])
  686
  
  See Also
  ========
  
  multiset_partitions_taocp
  sympy.utilities.iterables.multiset_partitions
  
  References
  ==========
  
  .. [AOCP] Algorithm 7.1.2.5M in Volume 4A, Combinatoral Algorithms,
         Part 1, of The Art of Computer Programming, by Donald Knuth.
  
  .. [Factorisatio] On a Problem of Oppenheim concerning
         "Factorisatio Numerorum" E. R. Canfield, Paul Erdos, Carl
         Pomerance, JOURNAL OF NUMBER THEORY, Vol. 17, No. 1. August
         1983.  See section 7 for a description of an algorithm
         similar to Knuth's.
  
  .. [Yorgey] Generating Multiset Partitions, Brent Yorgey, The
         Monad.Reader, Issue 8, September 2007.
docstr: Returns the number of partitions of a multiset whose components
  have the multiplicities given in ``multiplicities``.
  
  For larger counts, this method is much faster than calling one
  of the enumerators and counting the result.  Uses dynamic
  programming to cut down on the number of nodes actually
  explored.  The dictionary used in order to accelerate the
  counting process is stored in the ``MultisetPartitionTraverser``
  object and persists across calls.  If the user does not
  expect to call ``count_partitions`` for any additional
  multisets, the object should be cleared to save memory.  On
  the other hand, the cache built up from one count run can
  significantly speed up subsequent calls to ``count_partitions``,
  so it may be advantageous not to clear the object.
  
  Examples
  ========
  
  >>> from sympy.utilities.enumerative import MultisetPartitionTraverser
  >>> m = MultisetPartitionTraverser()
  >>> m.count_partitions([9,8,2])
  288716
  >>> m.count_partitions([2,2])
  9
  >>> del m
  
  Notes
  =====
  
  If one looks at the workings of Knuth's algorithm M [AOCP]_, it
  can be viewed as a traversal of a binary tree of parts.  A
  part has (up to) two children, the left child resulting from
  the spread operation, and the right child from the decrement
  operation.  The ordinary enumeration of multiset partitions is
  an in-order traversal of this tree, and with the partitions
  corresponding to paths from the root to the leaves. The
  mapping from paths to partitions is a little complicated,
  since the partition would contain only those parts which are
  leaves or the parents of a spread link, not those which are
  parents of a decrement link.
  
  For counting purposes, it is sufficient to count leaves, and
  this can be done with a recursive in-order traversal.  The
  number of leaves of a subtree rooted at a particular part is a
  function only of that part itself, so memoizing has the
  potential to speed up the counting dramatically.
  
  This method follows a computational approach which is similar
  to the hypothetical memoized recursive function, but with two
  differences:
  
  1) This method is iterative, borrowing its structure from the
     other enumerations and maintaining an explicit stack of
     parts which are in the process of being counted.  (There
     may be multisets which can be counted reasonably quickly by
     this implementation, but which would overflow the default
     Python recursion limit with a recursive implementation.)
  
  2) Instead of using the part data structure directly, a more
     compact key is constructed.  This saves space, but more
     importantly coalesces some parts which would remain
     separate with physical keys.
  
  Unlike the enumeration functions, there is currently no _range
  version of count_partitions.  If someone wants to stretch
  their brain, it should be possible to construct one by
  memoizing with a histogram of counts rather than a single
  count, and combining the histograms.
docstr_tok: ["Returns","the","number","of","partitions","of","a","multiset","whose","components","have","the","multiplicities","given","in","``","multiplicities","``",".","For","larger","counts",",","this","method","is","much","faster","than","calling","one","of","the","enumerators","and","counting","the","result",".","Uses","dynamic","programming","to","cut","down","on","the","number","of","nodes","actually","explored",".","The","dictionary","used","in","order","to","accelerate","the","counting","process","is","stored","in","the","``","MultisetPartitionTraverser","``","object","and","persists","across","calls",".","If","the","user","does","not","expect","to","call","``","count_partitions","``","for","any","additional","multisets",",","the","object","should","be","cleared","to","save","memory",".","On","the","other","hand",",","the","cache","built","up","from","one","count","run","can","significantly","speed","up","subsequent","calls","to","``","count_partitions","``",",","so","it","may","be","advantageous","not","to","clear","the","object",".","Examples","========",">",">",">","from","sympy.utilities.enumerative","import","MultisetPartitionTraverser",">",">",">","m","=","MultisetPartitionTraverser","(",")",">",">",">","m.count_partitions","(","[","9,8,2","]",")","288716",">",">",">","m.count_partitions","(","[","2,2","]",")","9",">",">",">","del","m","Notes","=====","If","one","looks","at","the","workings","of","Knuth","'s","algorithm","M","[","AOCP","]","_",",","it","can","be","viewed","as","a","traversal","of","a","binary","tree","of","parts",".","A","part","has","(","up","to",")","two","children",",","the","left","child","resulting","from","the","spread","operation",",","and","the","right","child","from","the","decrement","operation",".","The","ordinary","enumeration","of","multiset","partitions","is","an","in-order","traversal","of","this","tree",",","and","with","the","partitions","corresponding","to","paths","from","the","root","to","the","leaves",".","The","mapping","from","paths","to","partitions","is","a","little","complicated",",","since","the","partition","would","contain","only","those","parts","which","are","leaves","or","the","parents","of","a","spread","link",",","not","those","which","are","parents","of","a","decrement","link",".","For","counting","purposes",",","it","is","sufficient","to","count","leaves",",","and","this","can","be","done","with","a","recursive","in-order","traversal",".","The","number","of","leaves","of","a","subtree","rooted","at","a","particular","part","is","a","function","only","of","that","part","itself",",","so","memoizing","has","the","potential","to","speed","up","the","counting","dramatically",".","This","method","follows","a","computational","approach","which","is","similar","to","the","hypothetical","memoized","recursive","function",",","but","with","two","differences",":","1",")","This","method","is","iterative",",","borrowing","its","structure","from","the","other","enumerations","and","maintaining","an","explicit","stack","of","parts","which","are","in","the","process","of","being","counted",".","(","There","may","be","multisets","which","can","be","counted","reasonably","quickly","by","this","implementation",",","but","which","would","overflow","the","default","Python","recursion","limit","with","a","recursive","implementation",".",")","2",")","Instead","of","using","the","part","data","structure","directly",",","a","more","compact","key","is","constructed",".","This","saves","space",",","but","more","importantly","coalesces","some","parts","which","would","remain","separate","with","physical","keys",".","Unlike","the","enumeration","functions",",","there","is","currently","no","_range","version","of","count_partitions",".","If","someone","wants","to","stretch","their","brain",",","it","should","be","possible","to","construct","one","by","memoizing","with","a","histogram","of","counts","rather","than","a","single","count",",","and","combining","the","histograms","."]
code: def count_partitions(self, multiplicities):
      """Returns the number of partitions of a multiset whose components
      have the multiplicities given in ``multiplicities``.
  
      For larger counts, this method is much faster than calling one
      of the enumerators and counting the result.  Uses dynamic
      programming to cut down on the number of nodes actually
      explored.  The dictionary used in order to accelerate the
      counting process is stored in the ``MultisetPartitionTraverser``
      object and persists across calls.  If the user does not
      expect to call ``count_partitions`` for any additional
      multisets, the object should be cleared to save memory.  On
      the other hand, the cache built up from one count run can
      significantly speed up subsequent calls to ``count_partitions``,
      so it may be advantageous not to clear the object.
  
      Examples
      ========
  
      >>> from sympy.utilities.enumerative import MultisetPartitionTraverser
      >>> m = MultisetPartitionTraverser()
      >>> m.count_partitions([9,8,2])
      288716
      >>> m.count_partitions([2,2])
      9
      >>> del m
  
      Notes
      =====
  
      If one looks at the workings of Knuth's algorithm M [AOCP]_, it
      can be viewed as a traversal of a binary tree of parts.  A
      part has (up to) two children, the left child resulting from
      the spread operation, and the right child from the decrement
      operation.  The ordinary enumeration of multiset partitions is
      an in-order traversal of this tree, and with the partitions
      corresponding to paths from the root to the leaves. The
      mapping from paths to partitions is a little complicated,
      since the partition would contain only those parts which are
      leaves or the parents of a spread link, not those which are
      parents of a decrement link.
  
      For counting purposes, it is sufficient to count leaves, and
      this can be done with a recursive in-order traversal.  The
      number of leaves of a subtree rooted at a particular part is a
      function only of that part itself, so memoizing has the
      potential to speed up the counting dramatically.
  
      This method follows a computational approach which is similar
      to the hypothetical memoized recursive function, but with two
      differences:
  
      1) This method is iterative, borrowing its structure from the
         other enumerations and maintaining an explicit stack of
         parts which are in the process of being counted.  (There
         may be multisets which can be counted reasonably quickly by
         this implementation, but which would overflow the default
         Python recursion limit with a recursive implementation.)
  
      2) Instead of using the part data structure directly, a more
         compact key is constructed.  This saves space, but more
         importantly coalesces some parts which would remain
         separate with physical keys.
  
      Unlike the enumeration functions, there is currently no _range
      version of count_partitions.  If someone wants to stretch
      their brain, it should be possible to construct one by
      memoizing with a histogram of counts rather than a single
      count, and combining the histograms.
      """
      # number of partitions so far in the enumeration
      self.pcount = 0
  
      # dp_stack is list of lists of (part_key, start_count) pairs
      self.dp_stack = []
  
      self._initialize_enumeration(multiplicities)
      pkey = part_key(self.top_part())
      self.dp_stack.append(
          [
              (pkey, 0),
          ]
      )
      while True:
          while self.spread_part_multiplicity():
              pkey = part_key(self.top_part())
              if pkey in self.dp_map:
                  # Already have a cached value for the count of the
                  # subtree rooted at this part.  Add it to the
                  # running counter, and break out of the spread
                  # loop.  The -1 below is to compensate for the
                  # leaf that this code path would otherwise find,
                  # and which gets incremented for below.
  
                  self.pcount += self.dp_map[pkey] - 1
                  self.lpart -= 1
                  break
              else:
                  self.dp_stack.append(
                      [
                          (pkey, self.pcount),
                      ]
                  )
  
          # M4  count a leaf partition
          self.pcount += 1
  
          # M5 (Decrease v)
          while not self.decrement_part(self.top_part()):
              # M6 (Backtrack)
              for key, oldcount in self.dp_stack.pop():
                  self.dp_map[key] = self.pcount - oldcount
              if self.lpart == 0:
                  return self.pcount
              self.lpart -= 1
  
          # At this point have successfully decremented the part on
          # the stack and it does not appear in the cache.  It needs
          # to be added to the list at the top of dp_stack
          pkey = part_key(self.top_part())
          self.dp_stack[-1].append(
              (pkey, self.pcount),
          )
  
label_desc: Use image node_id 15 for calling the MultisetPartitionTraverser obj's underlying member method code with example usage: obj.count_partitions(multiplicities) and returns: self