List of integers & L.I.S.

[antonmuhin]

Hellom n00m!

I beg your pardon for not having replied for such long time---I was
really busy.

Yes, the posted code doesn't solve the supernumbers problem, but solves
the problem you posted first as I understood it :) --- for each number
find a position of this number in the longest sequence it belongs to.

Ok, anyway, I hope that I can suggest a solution to the supernumbers
problem (see below).

Actually, as I find out today testing it against Tim Peters's solution,
they are of the same kind, but I use one additional optimimization.

And the last note: I didn't persue the maximal performace, rather
clarity of the algorithm.

With the best regards,
anton.

from bisect import bisect as find

def supernumbers(l):
  indices = [0]*len(l)
  for i, e in enumerate(l):
    indices[e - 1] = i

  # Now we can find out index of each element in the longest ascending
sequence it belongs to
  # I call this index 'generation'

  # ess is an array indexed by generations and holding
  # ascending list of generation's elements
  #   Note: suffix s stands for a list, therefore ess---list of lists
of elements
  #   Note: ess holds not the elements itself, but elements decreased
by 1
  ess = []

  # Borders i.e. positions that separate generations
  borders = []

  for e, i in enumerate(indices):
    ind = find(borders, i)
    if ind < len(borders):
      borders[ind] = i
      ess[ind].append(e)
    else:
      borders.append(i)
      ess.append([e])

  # Now we should filter out those elements that don't
  #   belong to the longest sequences
  gens = reversed(ess) # walk generations in reverse order
  fes = gens.next() # fes stands for elements' filter
  r = fes # r is a list of supernumbers; obvioulsy all the elements of
the latest generation belong to r
  for es in gens:
    new_fes = []

    s = 0 # As elements are sorted ascendingly we can check lesser and
lesser lists
    for e in es:
      s = find(fes, e, s)
      if s == len(fes):
        # There is no more elements in filter that are greater
        #   than elements in the current generation
        break
      if indices[fes[s]] > indices[e]: # Nice---element e belongs to
the longest sequence
        new_fes.append(e)

    # Note: the following invariant holds: len(new_fes) > 0

    fes = new_fes
    r += new_fes

  return [e + 1 for e in r] # As we used numbers from 0 internally