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: Decrements part (a subrange of pstack), if possible, returning
  True iff the part was successfully decremented.
  
  Parameters
  ==========
  
  part
      part to be decremented (topmost part on the stack)
  
  ub
      the maximum number of parts allowed in a partition
      returned by the calling traversal.
  
  Notes
  =====
  
  The goal of this modification of the ordinary decrement method
  is to fail (meaning that the subtree rooted at this part is to
  be skipped) when it can be proved that this part can only have
  child partitions which are larger than allowed by ``ub``. If a
  decision is made to fail, it must be accurate, otherwise the
  enumeration will miss some partitions.  But, it is OK not to
  capture all the possible failures -- if a part is passed that
  should not be, the resulting too-large partitions are filtered
  by the enumeration one level up.  However, as is usual in
  constrained enumerations, failing early is advantageous.
  
  The tests used by this method catch the most common cases,
  although this implementation is by no means the last word on
  this problem.  The tests include:
  
  1) ``lpart`` must be less than ``ub`` by at least 2.  This is because
     once a part has been decremented, the partition
     will gain at least one child in the spread step.
  
  2) If the leading component of the part is about to be
     decremented, check for how many parts will be added in
     order to use up the unallocated multiplicity in that
     leading component, and fail if this number is greater than
     allowed by ``ub``.  (See code for the exact expression.)  This
     test is given in the answer to Knuth's problem 7.2.1.5.69.
  
  3) If there is *exactly* enough room to expand the leading
     component by the above test, check the next component (if
     it exists) once decrementing has finished.  If this has
     ``v == 0``, this next component will push the expansion over the
     limit by 1, so fail.
docstr_tok: ["Decrements","part","(","a","subrange","of","pstack",")",",","if","possible",",","returning","True","iff","the","part","was","successfully","decremented",".","Parameters","==========","part","part","to","be","decremented","(","topmost","part","on","the","stack",")","ub","the","maximum","number","of","parts","allowed","in","a","partition","returned","by","the","calling","traversal",".","Notes","=====","The","goal","of","this","modification","of","the","ordinary","decrement","method","is","to","fail","(","meaning","that","the","subtree","rooted","at","this","part","is","to","be","skipped",")","when","it","can","be","proved","that","this","part","can","only","have","child","partitions","which","are","larger","than","allowed","by","``","ub","``",".","If","a","decision","is","made","to","fail",",","it","must","be","accurate",",","otherwise","the","enumeration","will","miss","some","partitions",".","But",",","it","is","OK","not","to","capture","all","the","possible","failures","--","if","a","part","is","passed","that","should","not","be",",","the","resulting","too-large","partitions","are","filtered","by","the","enumeration","one","level","up",".","However",",","as","is","usual","in","constrained","enumerations",",","failing","early","is","advantageous",".","The","tests","used","by","this","method","catch","the","most","common","cases",",","although","this","implementation","is","by","no","means","the","last","word","on","this","problem",".","The","tests","include",":","1",")","``","lpart","``","must","be","less","than","``","ub","``","by","at","least","2",".","This","is","because","once","a","part","has","been","decremented",",","the","partition","will","gain","at","least","one","child","in","the","spread","step",".","2",")","If","the","leading","component","of","the","part","is","about","to","be","decremented",",","check","for","how","many","parts","will","be","added","in","order","to","use","up","the","unallocated","multiplicity","in","that","leading","component",",","and","fail","if","this","number","is","greater","than","allowed","by","``","ub","``",".","(","See","code","for","the","exact","expression",".",")","This","test","is","given","in","the","answer","to","Knuth","'s","problem","7.2.1.5.69",".","3",")","If","there","is","*","exactly","*","enough","room","to","expand","the","leading","component","by","the","above","test",",","check","the","next","component","(","if","it","exists",")","once","decrementing","has","finished",".","If","this","has","``","v","==","0","``",",","this","next","component","will","push","the","expansion","over","the","limit","by","1",",","so","fail","."]
code: def decrement_part_small(self, part, ub):
      """Decrements part (a subrange of pstack), if possible, returning
      True iff the part was successfully decremented.
  
      Parameters
      ==========
  
      part
          part to be decremented (topmost part on the stack)
  
      ub
          the maximum number of parts allowed in a partition
          returned by the calling traversal.
  
      Notes
      =====
  
      The goal of this modification of the ordinary decrement method
      is to fail (meaning that the subtree rooted at this part is to
      be skipped) when it can be proved that this part can only have
      child partitions which are larger than allowed by ``ub``. If a
      decision is made to fail, it must be accurate, otherwise the
      enumeration will miss some partitions.  But, it is OK not to
      capture all the possible failures -- if a part is passed that
      should not be, the resulting too-large partitions are filtered
      by the enumeration one level up.  However, as is usual in
      constrained enumerations, failing early is advantageous.
  
      The tests used by this method catch the most common cases,
      although this implementation is by no means the last word on
      this problem.  The tests include:
  
      1) ``lpart`` must be less than ``ub`` by at least 2.  This is because
         once a part has been decremented, the partition
         will gain at least one child in the spread step.
  
      2) If the leading component of the part is about to be
         decremented, check for how many parts will be added in
         order to use up the unallocated multiplicity in that
         leading component, and fail if this number is greater than
         allowed by ``ub``.  (See code for the exact expression.)  This
         test is given in the answer to Knuth's problem 7.2.1.5.69.
  
      3) If there is *exactly* enough room to expand the leading
         component by the above test, check the next component (if
         it exists) once decrementing has finished.  If this has
         ``v == 0``, this next component will push the expansion over the
         limit by 1, so fail.
      """
      if self.lpart >= ub - 1:
          self.p1 += 1  # increment to keep track of usefulness of tests
          return False
      plen = len(part)
      for j in range(plen - 1, -1, -1):
          # Knuth's mod, (answer to problem 7.2.1.5.69)
          if j == 0 and (part[0].v - 1) * (ub - self.lpart) < part[0].u:
              self.k1 += 1
              return False
  
          if j == 0 and part[j].v > 1 or j > 0 and part[j].v > 0:
              # found val to decrement
              part[j].v -= 1
              # Reset trailing parts back to maximum
              for k in range(j + 1, plen):
                  part[k].v = part[k].u
  
              # Have now decremented part, but are we doomed to
              # failure when it is expanded?  Check one oddball case
              # that turns out to be surprisingly common - exactly
              # enough room to expand the leading component, but no
              # room for the second component, which has v=0.
              if (
                  plen > 1
                  and part[1].v == 0
                  and (part[0].u - part[0].v)
                  == ((ub - self.lpart - 1) * part[0].v)
              ):
                  self.k2 += 1
                  self.db_trace("Decrement fails test 3")
                  return False
              return True
      return False
  
label_desc: Use image node_id 5 for calling the MultisetPartitionTraverser obj's underlying member method code with example usage: obj.decrement_part_small(part, ub) and returns: False, False, False, True, False