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
--
http://mail.python.org/mailman/listinfo/python-list
