text: r"""
  Gelfand-Tsetlin Patterns
  
  AUTHORS:
  
  - Travis Scrimshaw (2013-15-03): Initial version
  
  REFERENCES:
  
  .. [BBF] B. Brubaker, D. Bump, and S. Friedberg.
     Weyl Group Multiple Dirichlet Series: Type A Combinatorial Theory.
     Ann. of Math. Stud., vol. 175, Princeton Univ. Press, New Jersey, 2011.
  
  .. [GC50] I. M. Gelfand and M. L. Cetlin.
     Finite-Dimensional Representations of the Group of Unimodular Matrices.
     Dokl. Akad. Nauk SSSR **71**, pp. 825--828, 1950.
  
  .. [Tok88] T. Tokuyama.
     A Generating Function of Strict Gelfand Patterns and Some Formulas on
     Characters of General Linear Groups.
     J. Math. Soc. Japan **40** (4), pp. 671--685, 1988.
  """
  #*****************************************************************************
  #       Copyright (C) 2013 Travis Scrimshaw <tscrim@ucdavis.edu>
  #
  #  Distributed under the terms of the GNU General Public License (GPL)
  #
  #    This code is distributed in the hope that it will be useful,
  #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  #    General Public License for more details.
  #
  #  The full text of the GPL is available at:
  #
  #                  http://www.gnu.org/licenses/
  #*****************************************************************************
  
  from sage.structure.parent import Parent
  from sage.structure.list_clone import ClonableArray
  from sage.structure.unique_representation import UniqueRepresentation
  from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
  from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets
  from sage.misc.classcall_metaclass import ClasscallMetaclass
  from sage.misc.cachefunc import cached_method
  from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
  from sage.rings.all import ZZ
  from sage.combinat.partition import Partitions
  from sage.combinat.tableau import Tableau, SemistandardTableaux
  from sage.combinat.combinatorial_map import combinatorial_map
  from sage.misc.misc import prod
  
  class GelfandTsetlinPattern(ClonableArray):
      r"""
      A Gelfand-Tsetlin (sometimes written as Gelfand-Zetlin or Gelfand-Cetlin)
      pattern.  They were originally defined in [GC50]_.
  
      A Gelfand-Tsetlin pattern is a triangular array:
  
      .. MATH::
  
          \begin{array}{ccccccccc}
          a_{1,1} & & a_{1,2} & & a_{1,3} & & \cdots & & a_{1,n} \\
          & a_{2,2} & & a_{2,3} & & \cdots & & a_{2,n} \\
          & & a_{3,3} & &  \cdots & & a_{3,n} \\
          & & & \ddots \\
          & & & & a_{n,n}
          \end{array}
  
      such that `a_{i,j} \geq a_{i+1,j+1} \geq a_{i,j+1}`.
  
      Gelfand-Tsetlin patterns are in bijection with semistandard Young tableaux
      by the following algorithm. Let `G` be a Gelfand-Tsetlin pattern with
      `\lambda^{(k)}` being the `(n-k+1)`-st row (note that this is a partition).
      The definition of `G` implies
  
      .. MATH::
  
          \lambda^{(0)} \subseteq \lambda^{(1)} \subseteq \cdots \subseteq
          \lambda^{(n)},
  
      where `\lambda^{(0)}` is the empty partition, and each skew shape
      `\lambda^{(k)}/\lambda^{(k-1)}` is a horizontal strip. Thus define `T(G)`
      by inserting `k` into the squares of the skew shape
      `\lambda^{(k)}/ \lambda^{(k-1)}`, for `k=1,\dots,n`.
  
      To each entry in a Gelfand-Tsetlin pattern, one may attach a decoration of
      a circle or a box (or both or neither).  These decorations appear in the
      study of Weyl group multiple Dirichlet series, and are implemented here
      following the exposition in [BBF]_.
  
      .. NOTE::
  
          We use the "right-hand" rule for determining circled and boxed entries.
  
      .. WARNING::
  
          The entries in Sage are 0-based and are thought of as flushed to the
          left in a matrix. In other words, the coordinates of entries in the
          Gelfand-Tsetlin patterns are thought of as the matrix:
  
          .. MATH::
  
              \begin{bmatrix}
              g_{0,0} & g_{0,1} & g_{0,2} & \cdots & g_{0,n-2} & g_{n-1,n-1} \\
              g_{1,0} & g_{1,1} & g_{1,2} & \cdots & g_{1,n-2} \\
              g_{2,0} & g_{2,1} & g_{2,2} & \cdots \\
              \vdots & \vdots & \vdots \\
              g_{n-2,0} & g_{n-2,1} \\
              g_{n-1,0}
              \end{bmatrix}.
  
          However, in the discussions, we will be using the **standard**
          numbering system.
  
      EXAMPLES::
  
          sage: G = GelfandTsetlinPattern([[3, 2, 1], [2, 1], [1]]); G
          [[3, 2, 1], [2, 1], [1]]
          sage: G.pp()
            3     2     1
               2     1
                  1
          sage: G = GelfandTsetlinPattern([[7, 7, 4, 0], [7, 7, 3], [7, 5], [5]]); G.pp()
            7     7     4     0
               7     7     3
                  7     5
                     5
          sage: G.to_tableau().pp()
            1  1  1  1  1  2  2
            2  2  2  2  2  3  3
            3  3  3  4
      """
      # Note that the width == height, so len(gt) == len(gt[0]) except
      #   we don't have to check if it is the emtry GT pattern
      __metaclass__ = ClasscallMetaclass
  
      @staticmethod
      def __classcall_private__(self, gt):
          """
          Return ``gt`` as a proper element of :class:`GelfandTsetlinPatterns`.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[2,1],[1]])
              sage: G.parent()
              Gelfand-Tsetlin patterns
              sage: TestSuite(G).run()
          """
          return GelfandTsetlinPatterns()(gt)
  
      def check(self):
          """
          Check that this is a valid Gelfand-Tsetlin pattern.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: G([[3,2,1],[2,1],[1]]).check()
          """
          assert all( self[i-1][j] >= self[i][j] >= self[i-1][j+1]
                      for i in range(1, len(self)) for j in range(len(self[i])) )
  
      def _hash_(self):
          """
          Return the hash value of ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: gt = G([[3,2,1],[2,1],[1]])
              sage: hash(gt) == hash(gt)
              True
  
          Check that :trac:`14717` is fixed::
  
              sage: GT = GelfandTsetlinPattern([[2, 1, 0], [2, 0], [1]])
              sage: GT in {}
              False
          """
          return hash(tuple(map(tuple, self)))
  
      def _repr_diagram(self):
          """
          Return a string representation of ``self`` as a diagram.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: print G([[3,2,1],[2,1],[1]])._repr_diagram()
                3     2     1
                   2     1
                      1
          """
          ret = ''
          for i, row in enumerate(self):
              if i != 0:
                  ret += '\n'
              ret += '   '*i
              ret += '   '.join('%3s'%val for val in row)
          return ret
  
      def pp(self):
          """
          Pretty print ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: G([[3,2,1],[2,1],[1]]).pp()
                3     2     1
                   2     1
                      1
          """
          print self._repr_diagram()
  
      def _latex_(self):
          r"""
          Return a `\LaTeX` representation of ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: latex(G([[3,2,1],[2,1],[1]]))
              \begin{array}{ccccc}
              3 & & 2 & & 1 \\
              & 2 & & 1 & \\
              & & 1 & &
              \end{array}
              sage: latex(G([]))
              \emptyset
          """
          n = len(self)
          if n == 0:
              return "\\emptyset"
          ret = "\\begin{array}{" + 'c'*(n*2-1) + "}\n"
          for i, row in enumerate(self):
              if i > 0:
                  ret += " \\\\\n"
              ret += "& "*i
              ret += " & & ".join(repr(val) for val in row)
              ret += " &"*i
          return ret + "\n\\end{array}"
  
      @combinatorial_map(name='to semistandard tableau')
      def to_tableau(self):
          """
          Return ``self`` as a semistandard Young tableau.
  
          The conversion from a Gelfand-Tsetlin pattern to a semistandard Young
          tableaux is as follows. Let `G` be a Gelfand-Tsetlin pattern with
          `\lambda^{(k)}` being the `(n-k+1)`-st row (note that this is a
          partition).  The definition of `G` implies
  
          .. MATH::
  
              \lambda^{(0)} \subseteq \lambda^{(1)} \subseteq \cdots \subseteq
              \lambda^{(n)},
  
          where `\lambda^{(0)}` is the empty partition, and each skew shape
          `\lambda^{(k)} / \lambda^{(k-1)}` is a horizontal strip. Thus define
          `T(G)` by inserting `k` into the squares of the skew shape
          `\lambda^{(k)} / \lambda^{(k-1)}`, for `k=1,\dots,n`.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: elt = G([[3,2,1],[2,1],[1]])
              sage: T = elt.to_tableau(); T
              [[1, 2, 3], [2, 3], [3]]
              sage: T.pp()
                1  2  3
                2  3
                3
              sage: G(T) == elt
              True
          """
          ret = []
          for i, row in enumerate(reversed(self)):
              for j, val in enumerate(row):
                  if j >= len(ret):
                      if val == 0:
                          break
                      ret.append([i+1]*val)
                  else:
                      ret[j].extend([i+1]*(val-len(ret[j])))
          S = SemistandardTableaux()
          return S(ret)
  
      @cached_method
      def boxed_entries(self):
          """
          Return the position of the boxed entries of ``self``.
  
          Using the *right-hand* rule, an entry `a_{i,j}` is boxed if
          `a_{i,j} = a_{i-1,j-1}`; i.e., `a_{i,j}` has the same value as its
          neighbor to the northwest.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
              sage: G.boxed_entries()
              ((1, 0),)
          """
          ret = []
          for i in range(1, len(self)):
              for j in range(len(self[i])):
                  if self[i][j] == self[i-1][j]:
                      ret.append((i, j))
          return tuple(ret)
  
      @cached_method
      def circled_entries(self):
          """
          Return the circled entries of ``self``.
  
          Using the *right-hand* rule, an entry `a_{i,j}` is circled if
          `a_{i,j} = a_{i-1,j}`; i.e., `a_{i,j}` has the same value as its
          neighbor to the northeast.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
              sage: G.circled_entries()
              ((1, 1), (2, 0))
          """
          ret = []
          for i in range(1, len(self)):
              for j in range(len(self[i])):
                  if self[i][j] == self[i-1][j+1]:
                      ret.append((i, j))
          return tuple(ret)
  
      @cached_method
      def special_entries(self):
          """
          Return the special entries.
  
          An entry `a_{i,j}` is special if `a_{i-1,j-1} > a_{i,j} > a_{i-1,j}`,
          that is to say, the entry is neither boxed nor circled and is **not**
          in the first row. The name was coined by [Tok88]_.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
              sage: G.special_entries()
              ()
              sage: G = GelfandTsetlinPattern([[4,2,1],[4,1],[2]])
              sage: G.special_entries()
              ((2, 0),)
          """
          ret = []
          for i in range(1, len(self)):
              for j in range(len(self[i])):
                  if self[i-1][j] > self[i][j] and self[i][j] > self[i-1][j+1]:
                      ret.append((i, j))
          return tuple(ret)
  
      def number_of_boxes(self):
          """
          Return the number of boxed entries. See :meth:`boxed_entries()`.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
              sage: G.number_of_boxes()
              1
          """
          return len(self.boxed_entries())
  
      def number_of_circles(self):
          """
          Return the number of boxed entries. See :meth:`circled_entries()`.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[1]])
              sage: G.number_of_circles()
              2
          """
          return len(self.circled_entries())
  
      def number_of_special_entries(self):
          """
          Return the number of special entries. See :meth:`special_entries()`.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[4,2,1],[4,1],[2]])
              sage: G.number_of_special_entries()
              1
          """
          return len(self.special_entries())
  
      def is_strict(self):
          """
          Return ``True`` if ``self`` is a strict Gelfand-Tsetlin pattern.
  
          A Gelfand-Tsetlin pattern is said to be *strict* if every row is
          strictly decreasing.
  
          EXAMPLES::
  
              sage: GelfandTsetlinPattern([[7,3,1],[6,2],[4]]).is_strict()
              True
              sage: GelfandTsetlinPattern([[3,2,1],[3,1],[1]]).is_strict()
              True
              sage: GelfandTsetlinPattern([[6,0,0],[3,0],[2]]).is_strict()
              False
          """
          for row in self:
              if any(row[i] == row[i+1] for i in range(len(row)-1)):
                  return False
          return True
  
      def row_sums(self):
          r"""
          Return the list of row sums.
  
          For a Gelfand-Tsetlin pattern `G`, the `i`-th row sum `d_i` is
  
          .. MATH::
  
              d_i = d_i(G) = \sum_{j=i}^{n} a_{i,j}.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[5,3,2,1,0],[4,3,2,0],[4,2,1],[3,2],[3]])
              sage: G.row_sums()
              [11, 9, 7, 5, 3]
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[2]])
              sage: G.row_sums()
              [6, 4, 2]
          """
          return [sum(self[i][j] for j in range(len(self[i]))) \
                    for i in range(len(self))]
  
      def weight(self):
          r"""
          Return the weight of ``self``.
  
          Define the weight of `G` to be the content of the tableau to which `G`
          corresponds under the bijection between Gelfand-Tsetlin patterns and
          semistandard tableaux.  More precisely,
  
          .. MATH::
  
              \mathrm{wt}(G) = (d_n, d_{n-1}-d_n, \dots, d_1-d_2),
  
          where the `d_i` are the row sums.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPattern([[2,1,0],[1,0],[1]])
              sage: G.weight()
              (1, 0, 2)
              sage: G = GelfandTsetlinPattern([[4,2,1],[3,1],[2]])
              sage: G.weight()
              (2, 2, 3)
          """
          wt = [self.row_sums()[-1]] + [self.row_sums()[i-1]-self.row_sums()[i] for i in reversed(range(1,len(self[0])))]
          return tuple(wt)
  
      def Tokuyama_coefficient(self, name='t'):
          r"""
          Return the Tokuyama coefficient attached to ``self``.
  
          Following the exposition of [BBF]_, Tokuyama's formula asserts
  
          .. MATH::
  
              \sum_{G} (t+1)^{s(G)} t^{l(G)}
              z_1^{d_{n+1}} z_2^{d_{n}-d_{n+1}} \cdots z_{n+1}^{d_1-d_2}
              =
              s_{\lambda}(z_1,\dots,z_{n+1}) \prod_{i<j} (z_j+tz_i),
  
          where the sum is over all strict Gelfand-Tsetlin patterns with fixed
          top row `\lambda + \rho`, with `\lambda` a partition with at most
          `n+1` parts and `\rho = (n, n-1, \ldots, 1, 0)`, and `s_\lambda` is a
          Schur function.
  
          INPUT:
  
          - ``name`` -- (Default: ``'t'``) An alternative name for the
            variable `t`.
  
          EXAMPLES::
  
              sage: P = GelfandTsetlinPattern([[3,2,1],[2,2],[2]])
              sage: P.Tokuyama_coefficient()
              0
              sage: G = GelfandTsetlinPattern([[3,2,1],[3,1],[2]])
              sage: G.Tokuyama_coefficient()
              t^2 + t
              sage: G = GelfandTsetlinPattern([[2,1,0],[1,1],[1]])
              sage: G.Tokuyama_coefficient()
              0
              sage: G = GelfandTsetlinPattern([[5,3,2,1,0],[4,3,2,0],[4,2,1],[3,2],[3]])
              sage: G.Tokuyama_coefficient()
              t^8 + 3*t^7 + 3*t^6 + t^5
          """
          R = PolynomialRing(ZZ, name)
          t = R.gen(0)
          if self.is_strict() == False:
              return R(0)
          return (t+1)**(self.number_of_special_entries()) * t**(self.number_of_boxes())
  
  
  class GelfandTsetlinPatterns(Parent, UniqueRepresentation):
      """
      Gelfand-Tsetlin patterns.
  
      INPUT:
  
      - ``n`` -- The width or depth of the array, also known as the rank
  
      - ``k`` -- (Default: ``None``) If specified, this is the maximum value that
        can occur in the patterns
  
      - ``top_row`` -- (Default: ``None``) If specified, this is the fixed top
        row of all patterns
  
      - ``strict`` -- (Default: ``False``) Set to ``True`` if all patterns are
        strict patterns
  
      TESTS:
  
      Check that the number of Gelfand-Tsetlin patterns is equal to the number
      of semistandard Young tableaux::
  
          sage: G = GelfandTsetlinPatterns(3,3)
          sage: c = 0
          sage: from sage.combinat.crystals.kirillov_reshetikhin import partitions_in_box
          sage: for p in partitions_in_box(3,3):
          ...      S = SemistandardTableaux(p, max_entry=3)
          ...      c += S.cardinality()
          sage: c == G.cardinality()
          True
  
      Note that the top row in reverse of the Gelfand-Tsetlin pattern is the
      shape of the corresponding semistandard Young tableau under the bijection
      described in :meth:`GelfandTsetlinPattern.to_tableau()`::
  
          sage: G = GelfandTsetlinPatterns(top_row=[2,2,1])
          sage: S = SemistandardTableaux([2,2,1], max_entry=3)
          sage: G.cardinality() == S.cardinality()
          True
      """
      @staticmethod
      def __classcall_private__(cls, n=None, k=None, strict=False, top_row=None):
          """
          Return the correct parent based upon the inputs.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: G2 = GelfandTsetlinPatterns()
              sage: G is G2
              True
              sage: G = GelfandTsetlinPatterns(3,4, strict=True)
              sage: G2 = GelfandTsetlinPatterns(int(3),int(4), strict=True)
              sage: G is G2
              True
              sage: G = GelfandTsetlinPatterns(top_row=[3,1,1])
              sage: G2 = GelfandTsetlinPatterns(top_row=(3,1,1))
              sage: G is G2
              True
          """
          if top_row is not None:
              top_row = tuple(top_row)
              if any(top_row[i] < top_row[i+1] for i in range(len(top_row)-1)):
                  raise ValueError("The top row must be weakly decreasing")
              if n is not None and n != len(top_row):
                  raise ValueError("n must be the length of the specified top row")
              return GelfandTsetlinPatternsTopRow(top_row, strict)
          return super(GelfandTsetlinPatterns, cls).__classcall__(cls, n, k, strict)
  
      def __init__(self, n, k, strict):
          """
          Initialize ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: TestSuite(G).run()
              sage: G = GelfandTsetlinPatterns(3)
              sage: TestSuite(G).run()
              sage: G = GelfandTsetlinPatterns(3, 3)
              sage: TestSuite(G).run()
              sage: G = GelfandTsetlinPatterns(3, 3, strict=True)
              sage: TestSuite(G).run()
          """
          self._n = n
          self._k = k
          self._strict = strict
          # Note - if a top row is given, then n and k are not None
          if k is not None and (n is not None or strict):
              Parent.__init__(self, category=FiniteEnumeratedSets())
          else:
              Parent.__init__(self, category=InfiniteEnumeratedSets())
  
      def __contains__(self, gt):
          """
          Check to see if ``gt`` is in ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns()
              sage: [[3, 1],[2]] in G
              True
              sage: [[2, 3],[4]] in G
              False
              sage: [[3, 1],[0]] in G
              False
              sage: [] in G
              True
              sage: G = GelfandTsetlinPatterns(3,2)
              sage: [] in G
              False
              sage: [[2,0,0],[1,0],[1]] in G
              True
              sage: [[0,0],[0]] in G
              False
              sage: [[3,0,0],[2,0],[0]] in G
              False
              sage: G = GelfandTsetlinPatterns(3,strict=True)
              sage: [[2,1,0],[2,1],[1]] in G
              True
              sage: [[3,0,0],[3,0],[0]] in G
              False
          """
          if not isinstance(gt, (list, tuple, GelfandTsetlinPattern)):
              return False
          # Check if it has the correct width/depth (if applicable)
          if self._n is not None and len(gt) != self._n:
              return False
          # Check if it has the correct maximum value
          if self._k is not None and any( val > self._k for row in gt for val in row ):
              return False
          # Check if it is a GT pattern
          if not all( gt[i-1][j] >= gt[i][j] >= gt[i-1][j+1]
                      for i in range(1, len(gt)) for j in range(len(gt[i])) ):
              return False
          # Check if it is strict if applicable
          if self._strict and any( gt[i][j] == gt[i][j-1] for i in range(len(gt))
                  for j in range(1, len(gt[i])) ):
              return False
          return True
  
      def _repr_(self):
          """
          Return a string representation of ``self``.
  
          EXAMPLES::
  
              sage: GelfandTsetlinPatterns(4)
              Gelfand-Tsetlin patterns of width 4
              sage: GelfandTsetlinPatterns(4, 3, strict=True)
              Strict Gelfand-Tsetlin patterns of width 4 and max value 3
              sage: G = GelfandTsetlinPatterns(k=3, strict=True); G
              Strict Gelfand-Tsetlin patterns with max value 3
          """
          base = "Gelfand-Tsetlin patterns"
          if self._strict:
              base = "Strict " + base
          if self._n is not None:
              if self._k is not None:
                  return base + " of width %s and max value %s"%(self._n, self._k)
              return base + " of width %s"%self._n
          if self._k is not None:
              return base + " with max value %s"%self._k
          return base
  
      def _element_constructor_(self, gt):
          """
          Construct an element of ``self`` from ``gt``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(3, 3, strict=True); G
              Strict Gelfand-Tsetlin patterns of width 3 and max value 3
              sage: elt = G([[3,2,1],[2,1],[1]]); elt.pp()
                3     2     1
                   2     1
                      1
              sage: elt.parent()
              Strict Gelfand-Tsetlin patterns of width 3 and max value 3
          """
          if isinstance(gt, GelfandTsetlinPattern) and gt.parent() == self:
              return gt
          if isinstance(gt, Tableau):
              gt = [list(x) for x in reversed(gt.to_chain()[1:])]
              n = len(gt)
              for i in range(n):
                  while len(gt[i]) < n-i:
                      gt[i].append(0)
              if self._n is not None:
                  if len(gt) == 0:
                      gt = [[0]]
                  while self._n != len(gt):
                      gt.insert(0, gt[0][:] + [0])
              return self.element_class(self, gt)
          return self.element_class(self, list(gt))
  
      Element = GelfandTsetlinPattern
  
      def __iter__(self):
          """
          Iterate through ``self`` by using a backtracing algorithm.
  
          EXAMPLES::
  
              sage: L = list(GelfandTsetlinPatterns(3,3))
              sage: c = 0
              sage: from sage.combinat.crystals.kirillov_reshetikhin import partitions_in_box
              sage: for p in partitions_in_box(3,3):
              ...      S = SemistandardTableaux(p, max_entry=3)
              ...      c += S.cardinality()
              sage: c == len(L)
              True
              sage: G = GelfandTsetlinPatterns(3, 3, strict=True)
              sage: all(x.is_strict() for x in G)
              True
              sage: G = GelfandTsetlinPatterns(k=3, strict=True)
              sage: all(x.is_strict() for x in G)
              True
  
          Checking iterator when the set is infinite::
  
              sage: T = GelfandTsetlinPatterns()
              sage: it = T.__iter__()
              sage: [it.next() for i in range(10)]
              [[],
               [[1]],
               [[2]],
               [[1, 1], [1]],
               [[3]],
               [[2, 1], [1]],
               [[2, 1], [2]],
               [[1, 1, 1], [1, 1], [1]],
               [[4]],
               [[3, 1], [1]]]
              sage: T = GelfandTsetlinPatterns(k=1)
              sage: it = T.__iter__()
              sage: [it.next() for i in range(10)]
              [[],
               [[0]],
               [[1]],
               [[0, 0], [0]],
               [[1, 0], [0]],
               [[1, 0], [1]],
               [[1, 1], [1]],
               [[0, 0, 0], [0, 0], [0]],
               [[1, 0, 0], [0, 0], [0]],
               [[1, 0, 0], [1, 0], [0]]]
  
          Check that :trac:`14718` is fixed::
  
              sage: T = GelfandTsetlinPatterns(1,3)
              sage: list(T)
              [[[0]],
               [[1]],
               [[2]],
               [[3]]]
          """
          # Special cases
          if self._n is None:
              yield self.element_class(self, [])
              if self._k is None:
                  # Since both `n` and `k` are none, we need special consideration
                  #   while iterating, so we do so by specifying the top row by
                  #   using the iterator for partitions
                  n = 1
                  while True:
                      if self._strict:
                          P = Partitions(n, max_slope=-1)
                      else:
                          P = Partitions(n)
                      for p in P:
                          for x in GelfandTsetlinPatterns(top_row=tuple(p), strict=self._strict):
                              yield self.element_class(self, list(x))
                      n += 1
                  return
              for x in xrange(self._k+1):
                  yield self.element_class(self, [[x]])
              n = 2
              while not self._strict or n <= self._k+1:
                  for x in self._list_iter(n):
                      yield self.element_class(self, x)
                  n += 1
              return
          if self._n < 0:
              return
          if self._n == 0:
              yield self.element_class(self, [])
              return
          if self._n == 1:
              if self._k is not None:
                  for x in xrange(self._k+1):
                      yield self.element_class(self, [[x]])
              else:
                  k = 1
                  while True:
                      yield self.element_class(self, [[k]])
                      k += 1
              return
          for x in self._list_iter(self._n):
              yield self.element_class(self, x)
  
      def _list_iter(self, n):
          """
          Fast iterator which returns Gelfand-Tsetlin patterns of width ``n`` as
          lists of lists.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(3, 1)
              sage: L = [x for x in G._list_iter(3)]
              sage: len(L) == G.cardinality()
              True
              sage: type(L[0])
              <type 'list'>
          """
          # Setup the first row
          iters = [None]*n
          ret = [None]*n
          iters[0] = self._top_row_iter(n)
          ret[0] = iters[0].next()
          min_pos = 0
          iters[1] = self._row_iter(ret[0])
          pos = 1
          while pos >= min_pos:
              try:
                  ret[pos] = iters[pos].next()
                  pos += 1
                  # If we've reached 0 width, yield and backstep
                  if pos == n:
                      yield ret[:]
                      pos -= 1
                      continue
                  iters[pos] = self._row_iter(ret[pos-1])
              except StopIteration:
                  pos -= 1
  
      def _top_row_iter(self, n):
          """
          Helper iterator for the top row.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(3, 1)
              sage: for x in G._top_row_iter(3): x
              [0, 0, 0]
              [1, 0, 0]
              [1, 1, 0]
              [1, 1, 1]
              sage: G = GelfandTsetlinPatterns(3, 2, strict=True)
              sage: for x in G._top_row_iter(3): x
              [2, 1, 0]
          """
          row = [-1]*n
          pos = 0
          while pos >= 0:
              if pos == n:
                  yield row[:]
                  pos -= 1
                  continue
              # If it would create an invalid entry, backstep
              if ( pos > 0 and (row[pos] >= row[pos-1] \
                      or (self._strict and row[pos] == row[pos-1]-1)) ) \
                      or (self._k is not None and row[pos] >= self._k):
                  row[pos] = -1
                  pos -= 1
                  continue
              row[pos] += 1
              pos += 1
  
      def _row_iter(self, upper_row):
          """
          Helper iterator for any row with a row above it.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(3, 4)
              sage: for x in G._row_iter([4,2,1]): x
              [2, 1]
              [2, 2]
              [3, 1]
              [3, 2]
              [4, 1]
              [4, 2]
              sage: G = GelfandTsetlinPatterns(3, 2, strict=True)
              sage: for x in G._row_iter([2, 1, 0]): x
              [1, 0]
              [2, 0]
              [2, 1]
          """
          row = [x-1 for x in upper_row[1:]]
          row_len = len(row)
          pos = 0
          while pos >= 0:
              if pos == row_len:
                  yield row[:]
                  pos -= 1
                  continue
              # If it would create an invalid entry, backstep
              if ( pos > 0 and (row[pos] >= row[pos-1] \
                      or (self._strict and row[pos] == row[pos-1]-1)) ) \
                      or row[pos] >= upper_row[pos] \
                      or (self._k is not None and row[pos] >= self._k):
                  row[pos] = upper_row[pos+1] - 1
                  pos -= 1
                  continue
              row[pos] += 1
              pos += 1
  
  class GelfandTsetlinPatternsTopRow(GelfandTsetlinPatterns):
      """
      Gelfand-Tsetlin patterns with a fixed top row.
      """
      def __init__(self, top_row, strict):
          """
          Initialize ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(top_row=[4,4,3,1])
              sage: TestSuite(G).run()
  
          TESTS:
  
          Check a border case in :trac:`14765`::
  
              sage: G = GelfandTsetlinPatterns(top_row=[])
              sage: list(G)
              [[]]
          """
          self._row = top_row
          n = len(top_row)
          if n == 0:
              k = 0
          else:
              k = top_row[0]
          GelfandTsetlinPatterns.__init__(self, n, k, strict)
  
      def _repr_(self):
          """
          Return a string representation of ``self``.
  
          EXAMPLES::
  
              sage: GelfandTsetlinPatterns(top_row=[4,4,3,1])
              Gelfand-Tsetlin patterns with top row [4, 4, 3, 1]
              sage: GelfandTsetlinPatterns(top_row=[5,4,3,1], strict=True)
              Strict Gelfand-Tsetlin patterns with top row [5, 4, 3, 1]
          """
          base = "Gelfand-Tsetlin patterns with top row %s"%list(self._row)
          if self._strict:
              base = "Strict " + base
          return base
  
      def __contains__(self, gt):
          """
          Check if ``gt`` is in ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(top_row=[4,4,1])
              sage: [[4,4,1], [4,2], [3]] in G
              True
              sage: [[4,3,1], [4,2], [3]] in G
              False
          """
          # Check if the the top row matches (if applicable)
          if tuple(gt[0]) != self._row:
              return False
          return GelfandTsetlinPatterns.__contains__(self, gt)
  
      def __iter__(self):
          """
          Iterate over ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(top_row=[4,2,1])
              sage: list(G)
              [[[4, 2, 1], [2, 1], [1]],
               [[4, 2, 1], [2, 1], [2]],
               [[4, 2, 1], [2, 2], [2]],
               [[4, 2, 1], [3, 1], [1]],
               [[4, 2, 1], [3, 1], [2]],
               [[4, 2, 1], [3, 1], [3]],
               [[4, 2, 1], [3, 2], [2]],
               [[4, 2, 1], [3, 2], [3]],
               [[4, 2, 1], [4, 1], [1]],
               [[4, 2, 1], [4, 1], [2]],
               [[4, 2, 1], [4, 1], [3]],
               [[4, 2, 1], [4, 1], [4]],
               [[4, 2, 1], [4, 2], [2]],
               [[4, 2, 1], [4, 2], [3]],
               [[4, 2, 1], [4, 2], [4]]]
          """
          # If we enforce strictness, check to see if a specified top row is strict
          if self._strict and any(self._row[i] == self._row[i+1] for i in range(self._n-1)):
              return
          if self._n == 0:
              yield self.element_class(self, [])
              return
          if self._n == 1:
              yield self.element_class(self, [list(self._row)])
              return
          # Setup the first row
          iters = [None]*self._n
          ret = [None]*self._n
          ret[0] = list(self._row)
          min_pos = 1
          iters[1] = self._row_iter(ret[0])
          pos = 1
          while pos >= min_pos:
              try:
                  ret[pos] = iters[pos].next()
                  pos += 1
                  # If we've reached 0 width, yield and backstep
                  if pos == self._n:
                      yield self.element_class(self, ret[:])
                      pos -= 1
                      continue
                  iters[pos] = self._row_iter(ret[pos-1])
              except StopIteration:
                  pos -= 1
  
      def top_row(self):
          """
          Return the top row of ``self``.
  
          EXAMPLES::
  
              sage: G = GelfandTsetlinPatterns(top_row=[4,4,3,1])
              sage: G.top_row()
              (4, 4, 3, 1)
          """
          return self._row
  
      def Tokuyama_formula(self, name='t'):
          r"""
          Return the Tokuyama formula of ``self``.
  
          Following the exposition of [BBF]_, Tokuyama's formula asserts
  
          .. MATH::
  
              \sum_{G} (t+1)^{s(G)} t^{l(G)}
              z_1^{d_{n+1}} z_2^{d_{n}-d_{n+1}} \cdots z_{n+1}^{d_1-d_2}
              = s_{\lambda} (z_1, \ldots, z_{n+1}) \prod_{i<j} (z_j+tz_i),
  
          where the sum is over all strict Gelfand-Tsetlin patterns with fixed
          top row `\lambda+\rho`, with `\lambda` a partition with at most
          `n+1` parts and `\rho = (n,n-1,\dots,1,0)`, and `s_{\lambda}` is a Schur
          function.
  
          INPUT:
  
          - ``name`` -- (Default: ``'t'``) An alternative name for the
            variable `t`.
  
          EXAMPLES::
  
              sage: GT = GelfandTsetlinPatterns(top_row=[2,1,0],strict=True)
              sage: GT.Tokuyama_formula()
              t^3*x1^2*x2 + t^2*x1*x2^2 + t^2*x1^2*x3 + t^2*x1*x2*x3 + t*x1*x2*x3 + t*x2^2*x3 + t*x1*x3^2 + x2*x3^2
              sage: GT = GelfandTsetlinPatterns(top_row=[3,2,1],strict=True)
              sage: GT.Tokuyama_formula()
              t^3*x1^3*x2^2*x3 + t^2*x1^2*x2^3*x3 + t^2*x1^3*x2*x3^2 + t^2*x1^2*x2^2*x3^2 + t*x1^2*x2^2*x3^2 + t*x1*x2^3*x3^2 + t*x1^2*x2*x3^3 + x1*x2^2*x3^3
              sage: GT = GelfandTsetlinPatterns(top_row=[1,1,1],strict=True)
              sage: GT.Tokuyama_formula()
              0
          """
          n = self._n
          variables = [name] + ["x%d"%i for i in range(1,n+1)]
          R = PolynomialRing(ZZ,names=variables)
          t = R.gen(0)
          x = R.gens()[1:]
          GT = GelfandTsetlinPatterns(top_row=self._row, strict=True)
          return sum((t+1)**(gt.number_of_special_entries()) * t**(gt.number_of_boxes()) * prod(x[i]**gt.weight()[i] for i in range(n)) for gt in GT)
  