text: from itertools import combinations
  
  from sympy.combinatorics.graycode import GrayCode
  from sympy.core import Basic
  
  
  class Subset(Basic):
      """
      Represents a basic subset object.
  
      Explanation
      ===========
  
      We generate subsets using essentially two techniques,
      binary enumeration and lexicographic enumeration.
      The Subset class takes two arguments, the first one
      describes the initial subset to consider and the second
      describes the superset.
  
      Examples
      ========
  
      >>> from sympy.combinatorics.subsets import Subset
      >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
      >>> a.next_binary().subset
      ['b']
      >>> a.prev_binary().subset
      ['c']
      """
  
      _rank_binary = None
      _rank_lex = None
      _rank_graycode = None
      _subset = None
      _superset = None
  
      def __new__(cls, subset, superset):
          """
          Default constructor.
  
          It takes the ``subset`` and its ``superset`` as its parameters.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.subset
          ['c', 'd']
          >>> a.superset
          ['a', 'b', 'c', 'd']
          >>> a.size
          2
          """
          if len(subset) > len(superset):
              raise ValueError('Invalid arguments have been provided. The '
                               'superset must be larger than the subset.')
          for elem in subset:
              if elem not in superset:
                  raise ValueError('The superset provided is invalid as it does '
                                   'not contain the element {}'.format(elem))
          obj = Basic.__new__(cls)
          obj._subset = subset
          obj._superset = superset
          return obj
  
      def iterate_binary(self, k):
          """
          This is a helper function. It iterates over the
          binary subsets by ``k`` steps. This variable can be
          both positive or negative.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.iterate_binary(-2).subset
          ['d']
          >>> a = Subset(['a', 'b', 'c'], ['a', 'b', 'c', 'd'])
          >>> a.iterate_binary(2).subset
          []
  
          See Also
          ========
  
          next_binary, prev_binary
          """
          bin_list = Subset.bitlist_from_subset(self.subset, self.superset)
          n = (int(''.join(bin_list), 2) + k) % 2**self.superset_size
          bits = bin(n)[2:].rjust(self.superset_size, '0')
          return Subset.subset_from_bitlist(self.superset, bits)
  
      def next_binary(self):
          """
          Generates the next binary ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.next_binary().subset
          ['b']
          >>> a = Subset(['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.next_binary().subset
          []
  
          See Also
          ========
  
          prev_binary, iterate_binary
          """
          return self.iterate_binary(1)
  
      def prev_binary(self):
          """
          Generates the previous binary ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([], ['a', 'b', 'c', 'd'])
          >>> a.prev_binary().subset
          ['a', 'b', 'c', 'd']
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.prev_binary().subset
          ['c']
  
          See Also
          ========
  
          next_binary, iterate_binary
          """
          return self.iterate_binary(-1)
  
      def next_lexicographic(self):
          """
          Generates the next lexicographically ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.next_lexicographic().subset
          ['d']
          >>> a = Subset(['d'], ['a', 'b', 'c', 'd'])
          >>> a.next_lexicographic().subset
          []
  
          See Also
          ========
  
          prev_lexicographic
          """
          i = self.superset_size - 1
          indices = Subset.subset_indices(self.subset, self.superset)
  
          if i in indices:
              if i - 1 in indices:
                  indices.remove(i - 1)
              else:
                  indices.remove(i)
                  i = i - 1
                  while not i in indices and i >= 0:
                      i = i - 1
                  if i >= 0:
                      indices.remove(i)
                      indices.append(i+1)
          else:
              while i not in indices and i >= 0:
                  i = i - 1
              indices.append(i + 1)
  
          ret_set = []
          super_set = self.superset
          for i in indices:
              ret_set.append(super_set[i])
          return Subset(ret_set, super_set)
  
      def prev_lexicographic(self):
          """
          Generates the previous lexicographically ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([], ['a', 'b', 'c', 'd'])
          >>> a.prev_lexicographic().subset
          ['d']
          >>> a = Subset(['c','d'], ['a', 'b', 'c', 'd'])
          >>> a.prev_lexicographic().subset
          ['c']
  
          See Also
          ========
  
          next_lexicographic
          """
          i = self.superset_size - 1
          indices = Subset.subset_indices(self.subset, self.superset)
  
          while i >= 0 and i not in indices:
              i = i - 1
  
          if i == 0 or i - 1 in indices:
              indices.remove(i)
          else:
              if i >= 0:
                  indices.remove(i)
                  indices.append(i - 1)
              indices.append(self.superset_size - 1)
  
          ret_set = []
          super_set = self.superset
          for i in indices:
              ret_set.append(super_set[i])
          return Subset(ret_set, super_set)
  
      def iterate_graycode(self, k):
          """
          Helper function used for prev_gray and next_gray.
          It performs ``k`` step overs to get the respective Gray codes.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([1, 2, 3], [1, 2, 3, 4])
          >>> a.iterate_graycode(3).subset
          [1, 4]
          >>> a.iterate_graycode(-2).subset
          [1, 2, 4]
  
          See Also
          ========
  
          next_gray, prev_gray
          """
          unranked_code = GrayCode.unrank(self.superset_size,
                                         (self.rank_gray + k) % self.cardinality)
          return Subset.subset_from_bitlist(self.superset,
                                            unranked_code)
  
      def next_gray(self):
          """
          Generates the next Gray code ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([1, 2, 3], [1, 2, 3, 4])
          >>> a.next_gray().subset
          [1, 3]
  
          See Also
          ========
  
          iterate_graycode, prev_gray
          """
          return self.iterate_graycode(1)
  
      def prev_gray(self):
          """
          Generates the previous Gray code ordered subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([2, 3, 4], [1, 2, 3, 4, 5])
          >>> a.prev_gray().subset
          [2, 3, 4, 5]
  
          See Also
          ========
  
          iterate_graycode, next_gray
          """
          return self.iterate_graycode(-1)
  
      @property
      def rank_binary(self):
          """
          Computes the binary ordered rank.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset([], ['a','b','c','d'])
          >>> a.rank_binary
          0
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.rank_binary
          3
  
          See Also
          ========
  
          iterate_binary, unrank_binary
          """
          if self._rank_binary is None:
              self._rank_binary = int("".join(
                  Subset.bitlist_from_subset(self.subset,
                                             self.superset)), 2)
          return self._rank_binary
  
      @property
      def rank_lexicographic(self):
          """
          Computes the lexicographic ranking of the subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.rank_lexicographic
          14
          >>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
          >>> a.rank_lexicographic
          43
          """
          if self._rank_lex is None:
              def _ranklex(self, subset_index, i, n):
                  if subset_index == [] or i > n:
                      return 0
                  if i in subset_index:
                      subset_index.remove(i)
                      return 1 + _ranklex(self, subset_index, i + 1, n)
                  return 2**(n - i - 1) + _ranklex(self, subset_index, i + 1, n)
              indices = Subset.subset_indices(self.subset, self.superset)
              self._rank_lex = _ranklex(self, indices, 0, self.superset_size)
          return self._rank_lex
  
      @property
      def rank_gray(self):
          """
          Computes the Gray code ranking of the subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c','d'], ['a','b','c','d'])
          >>> a.rank_gray
          2
          >>> a = Subset([2, 4, 5], [1, 2, 3, 4, 5, 6])
          >>> a.rank_gray
          27
  
          See Also
          ========
  
          iterate_graycode, unrank_gray
          """
          if self._rank_graycode is None:
              bits = Subset.bitlist_from_subset(self.subset, self.superset)
              self._rank_graycode = GrayCode(len(bits), start=bits).rank
          return self._rank_graycode
  
      @property
      def subset(self):
          """
          Gets the subset represented by the current instance.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.subset
          ['c', 'd']
  
          See Also
          ========
  
          superset, size, superset_size, cardinality
          """
          return self._subset
  
      @property
      def size(self):
          """
          Gets the size of the subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.size
          2
  
          See Also
          ========
  
          subset, superset, superset_size, cardinality
          """
          return len(self.subset)
  
      @property
      def superset(self):
          """
          Gets the superset of the subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.superset
          ['a', 'b', 'c', 'd']
  
          See Also
          ========
  
          subset, size, superset_size, cardinality
          """
          return self._superset
  
      @property
      def superset_size(self):
          """
          Returns the size of the superset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.superset_size
          4
  
          See Also
          ========
  
          subset, superset, size, cardinality
          """
          return len(self.superset)
  
      @property
      def cardinality(self):
          """
          Returns the number of all possible subsets.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          >>> a.cardinality
          16
  
          See Also
          ========
  
          subset, superset, size, superset_size
          """
          return 2**(self.superset_size)
  
      @classmethod
      def subset_from_bitlist(self, super_set, bitlist):
          """
          Gets the subset defined by the bitlist.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> Subset.subset_from_bitlist(['a', 'b', 'c', 'd'], '0011').subset
          ['c', 'd']
  
          See Also
          ========
  
          bitlist_from_subset
          """
          if len(super_set) != len(bitlist):
              raise ValueError("The sizes of the lists are not equal")
          ret_set = []
          for i in range(len(bitlist)):
              if bitlist[i] == '1':
                  ret_set.append(super_set[i])
          return Subset(ret_set, super_set)
  
      @classmethod
      def bitlist_from_subset(self, subset, superset):
          """
          Gets the bitlist corresponding to a subset.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> Subset.bitlist_from_subset(['c', 'd'], ['a', 'b', 'c', 'd'])
          '0011'
  
          See Also
          ========
  
          subset_from_bitlist
          """
          bitlist = ['0'] * len(superset)
          if isinstance(subset, Subset):
              subset = subset.subset
          for i in Subset.subset_indices(subset, superset):
              bitlist[i] = '1'
          return ''.join(bitlist)
  
      @classmethod
      def unrank_binary(self, rank, superset):
          """
          Gets the binary ordered subset of the specified rank.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> Subset.unrank_binary(4, ['a', 'b', 'c', 'd']).subset
          ['b']
  
          See Also
          ========
  
          iterate_binary, rank_binary
          """
          bits = bin(rank)[2:].rjust(len(superset), '0')
          return Subset.subset_from_bitlist(superset, bits)
  
      @classmethod
      def unrank_gray(self, rank, superset):
          """
          Gets the Gray code ordered subset of the specified rank.
  
          Examples
          ========
  
          >>> from sympy.combinatorics.subsets import Subset
          >>> Subset.unrank_gray(4, ['a', 'b', 'c']).subset
          ['a', 'b']
          >>> Subset.unrank_gray(0, ['a', 'b', 'c']).subset
          []
  
          See Also
          ========
  
          iterate_graycode, rank_gray
          """
          graycode_bitlist = GrayCode.unrank(len(superset), rank)
          return Subset.subset_from_bitlist(superset, graycode_bitlist)
  
      @classmethod
      def subset_indices(self, subset, superset):
          """Return indices of subset in superset in a list; the list is empty
          if all elements of ``subset`` are not in ``superset``.
  
          Examples
          ========
  
              >>> from sympy.combinatorics import Subset
              >>> superset = [1, 3, 2, 5, 4]
              >>> Subset.subset_indices([3, 2, 1], superset)
              [1, 2, 0]
              >>> Subset.subset_indices([1, 6], superset)
              []
              >>> Subset.subset_indices([], superset)
              []
  
          """
          a, b = superset, subset
          sb = set(b)
          d = {}
          for i, ai in enumerate(a):
              if ai in sb:
                  d[ai] = i
                  sb.remove(ai)
                  if not sb:
                      break
          else:
              return list()
          return [d[bi] for bi in b]
  
  
  def ksubsets(superset, k):
      """
      Finds the subsets of size ``k`` in lexicographic order.
  
      This uses the itertools generator.
  
      Examples
      ========
  
      >>> from sympy.combinatorics.subsets import ksubsets
      >>> list(ksubsets([1, 2, 3], 2))
      [(1, 2), (1, 3), (2, 3)]
      >>> list(ksubsets([1, 2, 3, 4, 5], 2))
      [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), \
      (2, 5), (3, 4), (3, 5), (4, 5)]
  
      See Also
      ========
  
      Subset
      """
      return combinations(superset, k)
  