Getting the indices of the X largest numbers in a list

Question

Please no built-ins besides len() or range(). I'm studying for a final exam.

Here's an example of what I mean.

def find_numbers(x, lst):


lst = [3, 8, 1, 2, 0, 4, 8, 5]

find_numbers(3, lst) # this should return -> (1, 6, 7)

I tried this not fully....couldn't figure out the best way of going about it:

def find_K_highest(lst, k):
 newlst = [0] * k
 maxvalue = lst[0]


 for i in range(len(lst)):
    if lst[i] > maxvalue:
        maxvalue = lst[i]
        newlst[0] = i

Answer 1

Take the first 3 (x) numbers from the list. The minimum value for the maximum are these. In your case: 3, 8, 1. Their index is (0, 1, 2). Build pairs of them ((3,0), (8,1), (1,2)).

Now sort them by size of the maximum value: ((8,1), (3,0), (1,2)).

With this initial List, you can traverse the rest of the list recursively. Compare the smallest value (1, _) with the next element in the list (2, 3). If that is larger (it is), sort it into the list ((8,1), (3,0), (2,3)) and throw away the smallest.

In the beginning you have many changes in the top 3, but later on, they get rare. Of course you have to keep book about the last position (3, 4, 5, ...) too, when traversing.

An insertion sort for the top N elements should be pretty performant.

Here is a similar problem in Scala but without the need to report the indexes.

Answer 2

I dont know is it good to post a solution, but this seems to work:

def find_K_highest(lst, k):
    # escape index error
    if k>len(lst):
        k=len(lst)
    # the output array
    idxs = [None]*k
    to_watch = range(len(lst))
    # do it k times
    for i in range(k):
        # guess that max value is at least at idx '0' of to_watch
        to_del=0
        idx = to_watch[to_del]
        max_val = lst[idx]
        # search through the list for bigger value and its index
        for jj in range(len(to_watch)):
            j=to_watch[jj]
            val = lst[j]
            # check that its bigger that previously finded max
            if val > max_val:
                idx = j
                max_val = val
                to_del=jj
            # append it
        idxs[i] = idx
        del to_watch[to_del]
        # return answer
    return idxs

PS I tried to explain every line of code.

Answer 3

Can you use list methods? (e.g. append, sort, index?). If so, this should work (I think...)

def find_numbers(n,lst):
    ll=lst[:]
    ll.sort()
    biggest=ll[-n:]
    idx=[lst.index(i) for i in biggest] #This has the indices already, but we could have trouble if one of the numbers appeared twice
    idx.sort()
    #check for duplicates.  Duplicates will always be next to each other since we sorted.
    for i in range(1,len(idx)):
       if(idx[i-1]==idx[i]):
         idx[i]=idx[i]+lst[idx[i]+1:].index(lst[idx[i]]) #found a duplicate, chop up the input list and find the new index of that number
         idx.sort()
    return idx

lst = [3, 8, 1, 2, 0, 4, 8, 5]

print find_numbers(3, lst)

Answer 4

Dude. You have two ways you can go with this.

First way is to be clever. Phyc your teacher out. What she is looking for is recursion. You can write this with NO recursion and NO built in functions or methods:

#!/usr/bin/python

lst = [3, 8, 1, 2, 0, 4, 8, 5]

minval=-2**64

largest=[]

def enum(lst): 
    for i in range(len(lst)): 
        yield i,lst[i]

for x in range(3):
    m=minval
    m_index=None
    for i,j in enum(lst):
        if j>m: 
            m=j
            m_index=i

    if m_index:        
        largest=largest+[m_index]
        lst[m_index]=minval       

print largest  

This works. It is clever. Take that teacher!!! BUT, you will get a C or lower...

OR -- you can be the teacher's pet. Write it the way she wants. You will need a recursive max of a list. The rest is easy!

def max_of_l(l):
    if len(l) <= 1:
        if not l:
            raise ValueError("Max() arg is an empty sequence")
        else:
            return l[0]
    else:
        m = max_of_l(l[1:])
        return m if m > l[0] else l[0]

print max_of_l([3, 8, 1, 2, 0, 4, 8, 5])