title: Index into size ordered power set
body: <p>I would like to be able to index elements of a power set without expanding the full set into memory (a la itertools)</p>
  
  <p>Furthermore I want the index to be cardinality ordered. So index 0 should be the empty set, index 2**n - 1 should be all elements</p>
  
  <p>Most literature I have found so far involves generating a power set inductively. It doesn't let you just dive in at any index. My motivation for this indexing is to slice a problem for distributed execution and it be helpful if a remote machine can just dive in anywhere without sharing an iterator reference across a cluster.</p>
  
  <p>EDIT: Blckknght suggested the solution I pursued which is shown below</p>
  
  <pre><code>from scipy.misc import comb
  
  def kcombination_to_index(combination):
      index = 0
      combination = sorted(combination)
      for k, ck in enumerate(combination):
          index += comb(ck, k+1, exact=True)
      return index
  
  def index_to_kcombination(index, k):
      result = []
      for k in reversed(range(1, k+1)):
          n = 0
          while comb(n, k, exact=True) &lt;= index:
              n +=1
          result.append(n-1)
          index -= comb(n-1, k, exact=True)
  
      return result
  
  class PowerSet:
      def __init__(self, elements):
          self.elements = elements
  
      def __len__(self):
          return 2 ** len(self.elements)
  
      def __iter__(self):
          for i in range(len(self)):
              yield self[i]
  
      def __getitem__(self, k):
          if not isinstance(k, int):
              raise TypeError
          #k=0 is empty set,
          #k= 1 - 1+n returns subsets of size 1
          for subset_size in range(len(self.elements) + 1):
              number_subsets = comb(len(self.elements), subset_size, exact=True)
  
              if k &gt;= number_subsets:
                  k -= number_subsets
              else:
                  break
  
          #we now want the kth element of a possible permutation of subset_size elements
          indeces = index_to_kcombination(k, subset_size)
  
          return map(lambda i: self.elements[i], indeces)
  
  if __name__ == "__main__":
      print "index of combination [8, 6, 3, 1, 0] is", kcombination_to_index([8, 6, 3, 1, 0])
      print "5 combination at position 72 is", index_to_kcombination(72,5)
  
      ps = PowerSet(["a", "b", "c", "d"])
  
      for subset_idx in range(len(ps)):
          print ps[subset_idx]
  </code></pre>